[프로그래머스] 코딩테스트 연습 - 스타 수열 (Python)

코딩테스트 연습 - 스타 수열 [월간 코드 챌린지 시즌1]

코딩테스트 연습 - 스타 수열

참... 문제를 꼼꼼히 읽지 않아서 한참을 어렵게 생각했네요...

 

풀이

제가 해결한 풀이를 간단하게 적어보면 다음과 같습니다.

1. 3번 이상 연속되는 같은 수를 2개의 같은 수로 변경합니다.

2. 가장 빈도가 높은 수를 골라 스타 수열을 만듭니다.

 

먼저 스타수열을 만들기 위한 조건은 3가지가 있었죠.

1. 본래 수열의 순서를 유지
2. 스타 수열의 길이가 짝수
3. 차례대로 2개씩 묶었을 때 공통된 원소가 최소 하나 이상

 

간단하게 생각할 수 있는 방법은 가장 높은 빈도의 숫자를 골라 스타 수열을 만드는 방법입니다.

[5, 2, 3, 3, 5, 3]를 예로 들어보면 가장 높은 빈도의 숫자 3을 골라 스타수열을 만든다면 여러 가지 방법이 있겠지만 [2, 3, 3, 5] 또는 [5, 3, 3, 5]처럼 최대 길이는 4일 것입니다.

 

그러나 위의 방식을 사용하기에는 아직 반례들이 존재합니다.

예를 들어 [5, 2, 3, 3, 3, 3, 5, 5, 3]의 경우에서는 가장 5번의 빈도를 가진 숫자 3을 고르게 되면 3번의 빈도를 가진 숫자 5보다도 못한 스타 수열을 만들게 됩니다.

결국 여기서 확인할 수 있는 특징이 "3번 이상 연속되는 같은 수는 2개의 연속된 수와 만들 수 있는 스타 수열의 길이가 같다"입니다.

 

1. 3번 이상 연속되는 같은 수를 2개의 같은 수로 변경합니다.

저는 이러한 특징에 주목해서 주어진 수열 a에서 먼저 3번 이상 중복되는 같은 수를 2개의 같은 수로 변경하였습니다.

Ex) [5, 2, 3, 3, 3, 3, 5, 5, 3] -> [5, 2, 3, 3, 5, 5, 3]  # 3 두 개 제거

그리고 인덱스 (0번과 1번), (-1번과 -2번)의 수가 같으면 이 경우 역시 2개의 같은 수가 1개의 수와 만들 수 있는 스타 수열의 길이가 같아집니다. 왜냐하면 가장 끝에 있는 숫자 옆에는 하나의 숫자밖에 없는데 그 숫자가 같은 숫자라면 조건에 맞지 않기 때문입니다. 따라서 이러한 경우에서는 하나의 원소를 지우면 됩니다.

Ex) [5, 5, 2, 3, 3, 5, 3, 3] -> [5, 2, 3, 3, 5, 3]  # 맨 앞의 5 제거, 맨 뒤의 3 제거

 

2. 가장 빈도가 높은 수를 골라 스타 수열을 만듭니다.

위의 과정을 모두 거치고 나면 3개 이상의 연속되는 같은 숫자가 없는 배열이 만들어지게 됩니다.

해당 배열에서는 가장 높은 빈도의 숫자를 선택해서 해당 숫자를 기준으로 스타 수열을 만든다해도 문제될 것이 없습니다.

그럼 이제 처음 생각했던 방식을 그대로 적용해서 스타수열을 찾으면 \( O(2n) \)으로 문제를 해결할 수 있게 됩니다.

 

 

Code

from collections import Counter
def solution(a):
    if len(a) < 2: return 0
    answer = 0
    newarr, count = [a[0]], 1
    for ele in a[1:]:               # 연속되고 중복되는 숫자들 최대 2개로 줄이기
        if ele == newarr[-1] and count != 2:
            newarr.append(ele)
            count += 1
        elif ele != newarr[-1]:
            newarr.append(ele)
            count = 1

    if newarr[0] == newarr[1]:      # 1번과 2번이 같을 때 1개로 줄임
        newarr = newarr[1:]
    if newarr[-1] == newarr[-2]:    # -1번과 -2번이 같을 때 1개로 줄임
        newarr = newarr[:-1]

    target = Counter(newarr).most_common(1)[0][0]   # 가장 많은 수
    idx, first, second = 0, -1, -1
    while idx < len(newarr) - 1:    # 스타 수열 찾기
        if (newarr[idx] == newarr[idx + 1]) or (newarr[idx] != target and newarr[idx + 1] != target):
            idx += 1                # target이 되는 수가 없으면 continue
            continue
        answer += 1
        idx += 2

    return answer * 2

 

 

문제 설명

다음과 같은 것들을 정의합니다.

• 어떤 수열 x의 부분 수열(Subsequence)이란, x의 몇몇 원소들을 제거하거나 그러지 않고 남은 원소들이 원래 순서를 유지하여 얻을 수 있는 새로운 수열을 말합니다.
  • 예를 들어, [1,3]은 [1,2,3,4,5]의 부분수열입니다. 원래 수열에서 2, 4, 5를 제거해서 얻을 수 있기 때문입니다.
• 다음과 같은 조건을 모두 만족하는 수열 x를 스타 수열이라고 정의합니다.
  • x의 길이가 2 이상의 짝수입니다. (빈 수열은 허용되지 않습니다.)
  • x의 길이를 2n이라 할 때, 다음과 같은 n개의 집합 {x[0], x[1]}, {x[2], x[3]}, ..., {x[2n-2], x[2n-1]} 의 교집합의 원소의 개수가 1 이상입니다.
  • x[0] != x[1], x[2] != x[3], ..., x[2n-2] != x[2n-1] 입니다.
  • 예를 들어, [1,2,1,3,4,1,1,3]은 스타 수열입니다. {1,2}, {1,3}, {4,1}, {1,3} 의 교집합은 {1} 이고, 각 집합 내의 숫자들이 서로 다르기 때문입니다.

1차원 정수 배열 a가 매개변수로 주어집니다. a의 모든 부분 수열 중에서 가장 길이가 긴 스타 수열의 길이를 return 하도록 solution 함수를 완성해주세요. 이때, a의 모든 부분 수열 중에서 스타 수열이 없다면, 0을 return 해주세요.

 

 

제한사항

• a의 길이는 1 이상 500,000 이하입니다.
  • a의 모든 수는 0 이상 (a의 길이) 미만입니다.

 

 

입출력 예

a	result
[0]	0
[5,2,3,3,5,3]	4
[0,3,3,0,7,2,0,2,2,0]	8

 

입출력 예 #1

• a의 부분 수열 중에서 주어진 조건을 모두 만족하는 스타 수열이 없으므로, 0을 return 해야 합니다.

입출력 예 #2

• [5,2,5,3], [5,3,3,5] 는 a의 부분 수열인 동시에 스타 수열입니다. a의 부분 수열 중 이보다 더 긴 스타 수열은 없으므로, 4를 return 해야 합니다.

입출력 예 #3

• [0,3,3,0,7,0,2,0] 는 a의 부분 수열인 동시에 스타 수열입니다. a의 부분 수열 중 이보다 더 긴 스타 수열은 없으므로, 8을 return 해야 합니다.