문제

풀이

최대 길이가 500,000이므로 $O(n^2)$으로는 불가능하다. 그러니 뭔가 기준을 잡아야 하는데, 교집합의 원소를 기준으로 삼았을 때 스타 수열의 최대 길이는 그 원소 개수의 2배이므로 이를 이용했다. 이런 식으로 집합의 원소 개수가 필요할 때 collections 모듈의 Counter를 이용하면 편하다. 여태 딕셔너리를 생성해서 하나씩 세는 과정을 작성하는 게 은근 귀찮았는데 이 과정을 간편하게 구현할 수 있어 편리했다.

공통으로 들어갈 원소를 flag라고 두었을 때 배열을 순회하며 최대 길이로 만들도록 알고리즘을 구성했다. 현재 길이가 짝수라면 새로운 쌍을 추가할 차례이므로 값에 관계없이 추가하면 된다. 홀수일 경우 새롭게 만들어지는 쌍이 서로 다른 원소이면서 flag를 하나만 포함해야 한다. 이렇게 만들어진 배열의 길이가 홀수라면 1을 빼준다.

코드

from collections import Counter

def solution(a):
    # 교집합의 원소를 기준으로 세기
    count = Counter(a).most_common()
    answer = 0
    for flag, n in count:
        # n번 나오는 수로는 2n 길이까지 만들 수 있음
        if n * 2 < answer:
            break

        # 순서가 유지되므로 효율을 위해 마지막 원소만 기억
        last = None
        check = 0
        for x in a:
            if check % 2 == 0 or (last == flag) == (x != flag):
                check += 1
                last = x
        answer = max(answer, check - check % 2)

    return answer

사족

3단계 주제에 무려 4점...이긴 한데 이게 3단계인 게 잘못 아닐까 하는 생각도 들었다.

그리고 777위 달성했길래 왠지 기분 좋아서 찍어봤다.