[Programmers] 스타 수열 바로가기
다음과 같은 것들을 정의합니다.
어떤 수열 x의 부분 수열(Subsequence)이란, x의 몇몇 원소들을 제거하거나 그러지 않고 남은 원소들이 원래 순서를 유지하여 얻을 수 있는 새로운 수열을 말합니다.
[1,3]
은 [1,2,3,4,5]
의 부분수열입니다. 원래 수열에서 2, 4, 5를 제거해서 얻을 수 있기 때문입니다.다음과 같은 조건을 모두 만족하는 수열 x를 스타 수열이라고 정의합니다.
{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 | result |
---|---|
[0] | 0 |
[5,2,3,3,5,3] | 4 |
[0,3,3,0,7,2,0,2,2,0] | 8 |
입출력 예 #1
입출력 예 #2
[5,2,5,3]
, [5,3,3,5]
는 a의 부분 수열인 동시에 스타 수열입니다. a의 부분 수열 중 이보다 더 긴 스타 수열은 없으므로, 4를 return 해야 합니다.입출력 예 #3
[0,3,3,0,7,0,2,0]
는 a의 부분 수열인 동시에 스타 수열입니다. a의 부분 수열 중 이보다 더 긴 스타 수열은 없으므로, 8을 return 해야 합니다.from collections import defaultdict
def solution(a):
answer = 0
N = len(a)
# key를 교집합으로 갖는 스타수열의 길이
def lengthOfStarSequence(key, idxs):
count = 0
used = [True] * N
for i in idxs:
# 이미 사용한 원소인 경우
if not used[i]: continue
# 왼쪽 원소와 조합
if i > 0 and a[i] != a[i-1] and used[i-1]:
used[i] = False
count += 2
# 오른쪽 원소와 조합
elif i < (N-1) and a[i] != a[i+1] and used[i+1]:
used[i+1] = False
count += 2
return count
# { 원소 : [원소 인덱스...] }
dictionary = defaultdict(list)
for i in range(N):
dictionary[a[i]].append(i)
for key, idxs in dictionary.items():
# 가지치기
if len(idxs) * 2 < answer: continue
answer = max(answer, lengthOfStarSequence(key, idxs))
return answer