[프로그래머스] 월간 코드 챌린지 - 스타 수열, 파이썬

문제

---

• 프로그래머스 스타수열 링크

풀이

---

• 난이도 : 레벨 3
• 월간 코드챌린지가 뭔지는 모르겠으나 기업 코딩테스트용-스타일 문제는 아니다.
• 주어지는 배열 a의 최대 길이가 500,000 이기 때문에 O(N^2)으로는 시간초과가 나온다.
• 부분수열은 순서를 바꿀 수 없기 때문에 순서대로 a 배열을 순환하며 조건에 맞게 딕셔너리에 값을 넣어준 후 나중에 비교하였다.
• [0, 1, 0, 1]과 같은 순서는 문제 없으나 [0, 1, 1, 0], [1, 1, 0, 1]과 같은 자료는 문제가 될 수 있다.
• 따라서 위 케이스 등을 고려해서 문제에서 요구한 답을 O(N)으로 구할 수 있도록 코드를 짰다.

코드

---

from collections import defaultdict

def solution(a):
    N = len(a)
    if N < 2 :
        return 0
    dic, record = defaultdict(int), defaultdict(lambda : -2)
    for i in range(N - 1):
        cur, nxt = a[i], a[i+1]
        if cur != nxt:
            if record[cur] != i-1:
                dic[cur] += 2
                record[cur] = i
            if record[nxt] != i-1:
                dic[nxt] += 2
                record[nxt] = i
    return max(dic.values())