Programmers. 스타 수열

읽기 전

• 불필요한 코드나 잘못 작성된 내용에 대한 지적은 언제나 환영합니다.
• 개인적으로 배운 점을 정리한 글입니다.

문제 링크

Programmers. 스타 수열

문제 풀이

조건을 판별할 수 있는 로직을 잘 떠올려야 했다. 직관이 업으면 풀이 자체를 떠올릴 수 없는 문제라 생각한다. 어쩔 수 없이 경험이 좀 쌓여야하지 않을까.

스타 수열의 길이는 아무래도 공통 원소가 반드시 1개 이상이므로 가급적 배열 내의 원소의 개수에 종속될 것이다. 따라서 Counter 객체로 원소의 개수를 카운트한 뒤 많은 키 부터 현재 배열로 해당 원소를 교집합으로 갖는 스타 수열의 최대 길이를 산출하고 이를 모든 키에 반복하여 리턴하면 되겠다.

• a를 카운팅하는 Counter 객체 생성(키-빈도쌍)
• 빈도가 높은 키에 대해 반복문 정의
• 만약 빈도 수가 이전에 계산된 스타 수열의 길이 이하라면 최댓값 갱신이 불가하므로 skip
• idx = 0부터 탐색하되 현재 좌표와 다음 좌표의 값이 같거나 두 좌표에 탐색값이 없는 경우 다음 좌표로 진행
• 만약 위 조건에 해당되지 않는다면 스타수열을 만들 수 있으므로 카운트 1 올리고 2개의 원소가 매칭되었므로 좌표는 2를 더한다.

python 코드

from collections import Counter
def solution(a):
    if len(a) < 4:
        return 0
    counter = Counter(a)
    answer = -1
    for x in counter.keys():
        if counter[x] <= answer:
            continue
        i = 0
        cnt = 0
        while i < len(a) - 1:
            if (a[i] == a[i + 1]) or (a[i] != x and a[i + 1] != x):
                i += 1
            else:
                i += 2
                cnt += 1
        answer = max(answer, cnt)
    return answer * 2