[프로그래머스/Python] 스타 수열

 

📌문제 탐색하기

• 어떤 수열 x의 부분 수열 = x의 몇몇 원소들을 제거하거나, 제거하지 않고 남은 원소들이 원래의 순서를 유지하여 얻을 수 있는 새로운 수열
• 아래의 조건을 만족하는 수열 x = 스타 수열
  • 빈 수열이 아닌 x의 길이가 2 이상의 짝수
  • x의 길이를 2n이라 할 때, {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]
  • ex) [1, 2, 1, 3, 4, 1, 1, 3] / {1, 2}, {1, 3}, {4, 1}, {1, 3}의 교집합은 1, 각 집합 내 숫자가 서로 다름

매개변수

• 1차원 정수 배열 a가 매개 변수로 주어짐
  • 1 ≤ a의 길이 ≤ 500,000
  • 0 ≤ a의 모든 수 < a의 길이

반환값

• a의 모든 부분 수열 중에서 가장 길이가 긴 스타 수열의 길이
• 만약 a의 모든 부분 수열 중 스타 수열이 없다면 0

풀이 방법 생각해보기

주어진 a의 모든 부분 수열을 구해서 길이가 가장 긴 스타 수열을 구하는 것은 매우 비효율적이다. 스타 수열을 순서대로 두개씩 묶었을 때, 그 집합들의 교집합의 원소의 개수가 1이상이어야 하므로, 모든 집합에 겹치는 숫자가 하나씩 꼭 들어가야 한다는 말이 된다. a의 요소들의 빈도수를 구해 가장 빈도가 높은 순서대로, 해당 숫자가 교집합에 포함된다고 가정하고 스타 수열을 찾아나가는 것이 유리하다.

 

📌 코드 설계하기

1. a의 요소들의 빈도수를 collections.Counter로 구해 counts에 저장한다.
2. 스타 수열의 최대 길이를 저장할 변수 max_length를 0으로 초기화한다.
3. counts를 토대로, 빈도수가 가장 높은 순서대로 하나의 숫자(num)가 교집합에 포함된다고 가정하고 스타 수열의 길이를 구한다.
   1. 만약 (현재 숫자의 빈도수 * 2)를 했을 때, 현재 max_length의 길이를 넘지 못한다면 건너뛴다. 
   2. 교집합에 들어가는 숫자가 num일때의 스타 수열의 길이를 저장할 변수 length를 0으로 초기화한다. 
   3. a의 모든 요소를 하나씩 돌면서, a[i]가 num이거나 a[i+1]이 num이고, a[i]와 a[i+1]이 일치하지 않으면, length에 2를 더하고, 탐색 요소 인덱스(i)에도 2를 더한다.
   4. 3번의 조건을 만족하지 못했으면 i에 1을 더한다.
   5. 모든 요소에 대한 탐색이 끝나면 length를 토대로 max_length와 비교하여 갱신한다.
4. max_length를 반환한다.

 

 📌시도회차 수정사항

1회차

빈도수를 계산해야 한다는 생각을 전혀 하지 못해서, 다른 방법으로 시도해봤지만 잘 풀리지 않아 힌트를 받았다.

 

2회차

빈도수 계산을 했지만, 교집합에 포함될 숫자의 빈도수 * 2가 max_length보다 작거나 같을 때를 가지치기 해주지 않아 시간 초과가 발생했다.

 

 📌정답 코드

from collections import Counter

def solution(a):
    if len(a) == 1:
        return 0
    counts = Counter(a)
    max_length = 0
    
    for num, freq in counts.items():
        if freq * 2 <= max_length:
            continue
        
        length = 0
        i = 0
        while i < len(a)-1:
            if (a[i] == num or a[i+1] == num) and a[i] != a[i+1]:
                length += 2
                i += 2
            else:
                i += 1
        max_length = max(max_length, length)
    
    return max_length