[Programmers] 스타 수열 (월간 코드 챌린지 시즌1 - Level3, Python3)

 

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

 

문제 설명

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

• 어떤 수열 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

 

 

힌트

모든 부분 수열의 조합을 탐색하는 브루트포스 방식을 생각할 수도 있겠지만 제한 사항을 보면 a의 길이가 최대 50만이다. 모든 부분 수열을 탐색하려면 당연히 시간초과다.

 

이번 문제는 그리디(Greedy) 알고리즘을 사용하는 문제인데 비슷한 유형의 문제들을 풀어보지 않았다면 감이 안 올 수도 있다.

어느 정도 구현력을 요구하기도 해서 마냥 쉽지만은 않은 문제다.

 

그리디 알고리즘은 주로 구하고자 하는 해답의 목적에 중심을 두면 해결법을 찾기 수월하다.

이 문제의 최종 목적은 a의 부분 수열 중 가장 길이가 긴 스타 수열을 찾는 것이다.

스타 수열의 길이가 길기 위해서는 모든 집합에 공통인 원소가 1개 이상 있어야 하므로 수열에서 각 원소의 개수를 파악한 후에 개수가 가장 많은 순서로 탐색하면 된다.

 

 

풀이

방법은 여러 가지가 있겠지만 여기서는 탐색 과정에서 공통인 원소를 스타 수열에 포함시키기  위해 해당 원소의 왼쪽부터 스타 수열에 포함될 수 있는지 확인하였다.

 

힌트에서 주어진대로 해도 시간초과에 걸리기 십상이다.

원소의 개수가 많은 순서로 탐색을 해도 여기서 더 시간을 줄이기 위해 탐색을 할 필요가 없는 부분은 탐색하지 않았다.

 

def solution(a):
    counter = {}
    counter_list = set()
    answer = 0
    length = len(a)

    for i in a:
        counter[i] = counter.get(i, 0) + 1
    
    for val, count in counter.items():
        counter_list.add((count, val))

    for count, val in sorted(counter_list, reverse=True):
        if count <= answer:
            break

        chk = [0] * length

        for ind, number in enumerate(a):
            if number == val:
                if ind and not chk[ind - 1] and a[ind - 1] != number:
                    chk[ind] = 1
                    chk[ind - 1] = 1
                
                elif ind != length - 1 and not chk[ind + 1] and a[ind + 1] != number:
                    chk[ind] = 1
                    chk[ind + 1] = 1
        
        answer = max(answer, sum(chk) // 2)

        if count == answer:
            break

    return answer * 2