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

https://programmers.co.kr/learn/courses/30/lessons/70130

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

 

교집합이 될 수 있는 원소의 index 를 가지고 스타 수열의 길이를 구한다.

 

스타 수열의 최대 길이를 구하려고 한다면 우선 교집합의 원소가 오른쪽에 오는 것을 우선으로 한다.

또한, 스타 수열의 항에서 교집합의 원소랑 아닌 원소랑은 가장 근접한 것을 우선으로 한다.

 

조건에 맞는 항을 구한 후, 항의 각 원소가 다르면 스타 수열의 길이가 2씩 늘어난다.

 

from collections import defaultdict

def solution(a):
    answer = 0
    dic = defaultdict(list)
    N = len(a)
    
    for i in range(N):
        dic[a[i]].append(i)

    for i in dic.keys():
        if answer // 2 >= len(dic[i]):
            continue
            
        else:
            b = 0
            c = 0
            
            for j in dic[i]:
                if b >= j:
                    if j + 1 <= N - 1 and a[j] != a[j+1]:
                        c += 1

                    b = j + 2 

                else:
                    if a[j-1] != a[j]:
                        c += 1

                    b = j + 1 

            answer = max(answer, 2 * c) 
                
    return answer

print(solution([0])) # 0