[Python] 프로그래머스. 스타 수열 (Level 3)

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

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

문제의 조건에 따르면 "스타수열을 생성하기 위한 핵심 공통값"이 반드시 존재해야 한다.

• {x[0], x[1]} ... {x[2n-2], x[2n-1]} 의 공통원소가 1개 이상이기 위해서는, 각 쌍마다 공통값이 최소 한 개는 있어야 한다는 의미.

따라서, a 배열에 있는 각각의 원소를 기준으로 '해당 원소가 공통값으로 적용되는 스타수열의 길이' 최댓값을 찾아야 한다.

 

이 때, 각 원소가 a 배열에 몇 번 등장했는지가 중요하다.

배열에 등장한 횟수가 많을수록, 스타 수열의 길이가 길어질 수 있기 때문.

 

예컨대 입출력 예시 #3을 보면

[0,3,3,0,7,0,2,0] 배열에서 0은 4번, 3은 2번 존재한다.

0이 4개 있으므로, 생성할 수 있는 스타수열의 최대 길이는 [0,3,3,0,7,0,2,0]로 8까지 가능하지만

3은 2개뿐이므로, 2개인 3을 전부 사용한다 해도 [0,3,3,0]로 4까지만 가능하기 때문.

 

따라서, 배열의 원소가

• 이미 찾아낸 스타수열의 최대 길이 ( = 배열에서 해당 원소가 등장한 횟수)보다 작을 경우
  탐색할 필요가 없다. 최댓값 갱신이 불가능하기 때문

 

이곳의 해설을 참고했다.

yabmoons.tistory.com/610

[ 프로그래머스 [ 월간코드챌린지 ] 스타 수열 ] (C++)