[프로그래머스 Lv.3] 스타수열

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

프로그래머스

문제 접근이 어려워서 풀이를 참고했습니다.

 

첫번째로 스타수열의 조건을 따져야겠죠.

스타수열은 길이가 짝수이고

2개씩 나눴을 때 공통된 게 적어도 하나 이상.

그리고 그 나눈 수열의 원소가 같아서는 안됩니다.

 

가장 중요한 부분은

"공통된 게 적어도 하나 있다"

라는 부분이라고 생각했습니다.

그럼 이 공통된 게 어떻게 있는지 보는 것이

이 문제를 푸는데에 포인트라고 볼 수 있습니다.

 

검색한 결과, Counter라는 함수를 쓰면 간단하다는 걸 알아서

이를 참고해서 문제를 풀게 되었습니다.

 

from collections import Counter


def solution(a):
    # 각 원소의 등장횟수를 카운트
    answer = -1
    e = Counter(a)

    # 각 원소를 기준으로 스타수열을 만들 수 있는지 확인한다
    for k in e.keys():
        # 만약 원소가 최대로 만들 수 있는 것보다 적다면 굳이 더 볼 필요가 없다
        if e[k] < answer:
            continue

        common_cnt = 0
        idx = 0
        while idx < len(a) - 1:
            # 조건 만족하지 않으면 넘김
            # 두 구간의 원소가 같거나 공통원소가 없거나
            if a[idx] == a[idx + 1] or (a[idx] != k and a[idx + 1] != k):
                idx += 1
                continue

            common_cnt += 1
            idx += 2

        answer = max(common_cnt, answer)
    return answer * 2

https://inspirit941.tistory.com/316

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

참고한 풀이입니다.

 

프로그래머스는 lv3로 가면서

체감적으로 확 어려워지는 느낌...