문제 설명

전체 코드

from collections import Counter
# Counter을 사용하여 a 리스트의 요소 갯수를 dict형태로 내림차순으로 찾아낸다.

def solution(a):
    elements = Counter(a)
    answer = -1

    # k를 기준으로 스타수열을 만들 수 있는지 확인.
    for k in elements.keys():
        # k의 등장횟수가 스타수열에 사용된 공통인자 횟수보다 작거나 같으면
        # 더 계산할 필요가 없으므로
        if elements[k] <= answer:
            continue

        common_cnt = 0
        idx = 0

        while idx < len(a)-1:
            # a[idx]와 a[idx+1] 둘 다 k가 없는 경우: 공통값 k가 없다.
            # a[idx] == a[idx+1]인 경우: 조건에 위배
            if (a[idx] != k and a[idx+1] != k) or (a[idx] == a[idx+1]):
                idx += 1
                continue

            # 스타 원소로 추가할 수 있는 경우, k 원소가 사용된 횟수를 1 증가시킨다.
            common_cnt += 1
            # 다음 배열 탐색을 위해서는, idx를 2 증가시킨다. 
            idx += 2

        answer = max(common_cnt, answer)

    if answer == -1:
        return 0
    else:
        return answer * 2

해결 방법

이 문제는 문제 설명을 정확하게 이해한 다음 풀어야 하는 문제이다. 가장 중요한 핵심포인트는 공통원소가 1개 이상으로 각 쌍마다 공통값이 최소 1개는 있어야 한다는 조건이다.
이 때, 각 원소가 a배열의 몇 번 등장했는지를 본다. 배열의 등장한 횟수가 많을수록, 스타 수열의 길이가 길어지기 때문이다.

예시 3을 본다면 [0,3,3,0,7,0,2,0] 배열에서 0이 4번으로 가장 많이 나오므로 최대 길이는 8까지 가능한 것을 볼 수 있다. 하지만 3은 2번 밖에 안나오므로 최대 4의 길이만 가능하다.

따라서 배열의 원소가 스타수열의 최대길이(배열에서 해당 원소가 등장한 횟수)보다 작을 경우는 탐색할 필요가 없다.

도저히 혼자 힘으로 못풀어서 다른 곳의 해설을 참조 했다. level3 어려워ㅠㅠ

• 참고한 사이트: https://inspirit941.tistory.com/316