[Python] 프로그래머스 / 월간 코드 챌린지 시즌1 / 스타 수열

문제 링크

 

하란다고 진짜로 하지 말기

요즘 이런 식의 문제를 많이 풀어서 느껴지는 거지만, 문제에서 정의내리는 "부분수열"을 진짜로 만들어서 그것이 스타수열인지 체크하고... 하는 것은 불가능하다. 리스트에서 원소 하나 삭제하고 할 때마다 O(N)인데, 그걸 2^N 번을 반복해서 탐색한다?

*왜 2^N번 반복이냐면 nC0 + nC1 + nC2 + ... + nCn = 2^n 이니까

 

O(N*2^N) 같은 건, N이 24 이하여야 가능하다. 

 

그런데 N이 500,000까지 치솟을 수 있는 상황에서 저 복잡도는 그냥 말도 안 되는 소리이다.

 

언제나 본질을 기억하자. 부분수열을 만들어서 뭘 한다고 해서 "진짜로" 그걸 만들 필요는 없다.

 

정답 코드

from collections import Counter, deque

def solution(a):
    count_a = Counter(a)
    max_answer = 0
    n = len(a)
    
    if n < 2:
        return 0 
    
    for star in count_a:
        if count_a[star] * 2 <= max_answer:
            continue  
        
        deque_a = deque(a)
        answer = 0
        
        while len(deque_a) > 1:
            elem1 = deque_a.popleft()
            elem2 = deque_a.popleft()

            if (elem1 == star or elem2 == star) and elem1 != elem2:
                answer += 2  
            else:
                deque_a.appendleft(elem2) 
                
        max_answer = max(max_answer, answer)  

    return max_answer