[프로그래머스 - Python] 스타 수열

https://school.programmers.co.kr/learn/courses/30/lessons/70130?language=python3

프로그래머스

문제 요약

스타 수열 x의 조건
- x의 길이가 2 이상의 짝수
- 2개 단위로 나눈 집합들의 교집합 원소가 1개 이상
- 2개 단위로 나눈 집합들은 서로 다른 수
⇒ a의 모든 부분 수열 중에서 가장 길이가 긴 스타 수열의 길이를 반환
⇒ 없다면 0 반환

[스타 수열을 만족하려면]
1. 특정 원소를 최대한 많이 포함해야 함
2. 해당 원소와 함께 나올 수 있는 다른 원소를 찾아 짝을 이루어야 함

 

코드 설명

from collections import Counter

def solution(a):
    # 길이가 1이면 스타 수열을 만들 수가 없음
    if len(a) == 1:
        return 0
    
    counter = Counter(a)
    answer = 0
    
    for key in counter:
        if counter[key] * 2 <= answer:
            continue
        
        length = 0
        i = 0
        while i < len(a) - 1:
            # 스타 수열의 조건을 조건식으로 표현한 부분
            if (a[i] == key or a[i+1] == key) and a[i] != a[i+1]:
                length += 2
                i += 2    # 다음 쌍 탐색
            else:
                i += 1
                
        answer = max(answer, length)
    
    
    return answer

 

문제를 읽고, 수열에서 가장 많이 등장하는 원소를 기준으로 생각해야겠다는 생각까지 했다.

가장 많이 등장하는 원소를 셀 생각에서 막혔는데, collections 라이브러리의 Counter를 사용하면 쉽게 셀 수 있었다.

 

가장 많이 등장하는 원소가 부분 수열에서 2개 단위로 짝을 이루면서도,

그 짝의 2개의 원소는 서로 다른 수여야 하기 때문에 아래와 같은 조건식을 세울 수 있다.

if (a[i] == key or a[i+1] == key) and a[i] != a[i+1]

 

인덱스 i를 통해 수열의 숫자들에 접근하여

수열의 숫자들을 2개의 쌍으로 확인하는 것이 용이하도록 구현하였다.

 

한 쌍을 확인해서 조건을 만족하면 i를 2만큼 늘리고,

조건을 만족하지 않으면 1만큼만 늘린다.

이를 통해, 부분수열 조건을 만족하면서도 최대 길이의 스타 수열을 구할 수 있다.

 

모든 key 값에 대해서 위의 과정을 수행하여,

다른 key값으로 수행을 했을 시의 스타수열 길이와 비교하여

최장 스타 수열의 길이를 구한다.

 

배운 점

- Counter 클래스를 통해 쉽게 원소별 개수를 셀 수 있다.

- Counter 클래스를 반복문의 iterable로 사용하여, 각 원소값과 개수를 활용할 수 있다.

- 일정 범위를 건너뛰면서 조건을 확인해야 할 때는 인덱스 값으로 특정 변수를 활용하면 유용하다.