프로그래머스. 스타 수열

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

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

 

스타수열의 조건은

1) 크기가 2이상

2) 인접한 숫자와 크기 2씩 묶어 부분수열을 만든다면, 모든 부분수열들이 공통된 값을 1개 이상 갖고있어야 한다.

3) 2번과 같이 크기 2씩 묶어서 부분수열을 만들었을때, 모든 부분수열들의 두 숫자는 서로 달라야한다.

 

이 조건들 중, 스타수열의 길이를 결정하는 조건은 2번 조건이다.

결국 스타수열의 크기 2인 모든 부분수열들에는 같은 숫자가 1개 있어야 한다. (부분수열의 두 숫자는 서로 달라야 하므로 1개만 있을수 있다)

그 말은 즉, 주어지는 수열 a에서 가장 많이 출연하는 숫자가 스타수열의 교집합이 되는 그 숫자가 될 가능성이 있다는 뜻이다.

 

따라서 먼저 주어지는 수열 a에서 출연하는 모든 숫자들이 각각 몇번 출연하는지 카운팅하고,

가장 많이 출연하는 숫자부터, 해당하는 숫자가 포함되는 스타수열의 크기가 몇인지 세어보면 된다.

그렇게 특정 숫자가 포함되는 스타수열의 길이를 구하고,

다음으로 많이 출연하는 숫자의 갯수 * 2가 이전에 구한 스타수열의 길이보다 작다면 더이상 구해보지 않아도 된다.