[프로그래머스: 스타 수열] (Python)

문제링크 https://school.programmers.co.kr/learn/courses/30/lessons/70130

프로그래머스

 

접근 방법 & 문제풀이 

• 스타 수열은 앞에서부터 2개씩 나누었을 때 공통인 원소가 존재한다.
  단, 2개씩 나눈 두 원소는 서로 다름 
• 스타 수열의 길이가 최대가 되기 위해서는 빈도가 큰 원소부터 살펴보면서 
  스타 수열의 공통되는 원소라고 가정할 때 가능한 수열의 길이를 살펴본다.
• 이때, 해당 원소를 기준으로 사이에 존재하는 해당 원소가 아닌 원소의 갯수를 구하는 배열을 정의한다.
  이를 이용해 해당 원소와 짝꿍(?)이 가능한 원소가 존재하는지 판단한다 
• 처음에 가장 큰 빈도를 가진 원소가 스타수열의 공통 원소가 된다고 생각해 하나만 살펴봤지만 
  빈도수가 가장 큰 원소가 아니더라도 스타 수열의 길이가 더 길 수 있다는 반례가 존재했음.
  따라서, 빈도가 큰 순서대로 공통 원소라고 할때 스타수열의 길이의 최대값을 갱신하는 로직으로 반례 해결 
• 이때,  스타 수열의 최대 길이가 해당 원소의 갯수보다 작을 때 가지치기 하기! 

말로 설명하기 너무 어려운 문제ㅠㅠ,,  코드에 주석 자세히 달아놓을게요!

 

 

코드

from collections import Counter #조합 라이브러리 
def solution(a):
     #길이가 2보다 작으면 스타수열 불가능
    if len(a)<2:
        return 0 
    #길이가 2일때 원소가 서로 다르면 스타수열의 길이도 2, 서로 같으면 스타수열 불가능 
    if len(a) == 2: 
        if a[0] == a[1]:
            return 0
        else:
            return 2
        
    n = len(a)
    
    most = Counter(a).most_common() #원소를 빈도수에 따라 내림차순으로 정렬된 리스트 반환 
    max_ans = 0 #만들 수 있는 스타수열의 최대 길이/2 (스타수열의 길이= 공통 원소의 갯수*2)
    for num, cnt in most: ## 28번 테스트케이스 반례 -> 가장 빈도가 가장 큰 원소가 스타수열의 공통 원소가 아닐 수 있음. 빈도수 작은 숫자가 오히려 더 긴 스타 수열을 만들 수 있음!, 그래서, 모든 경우 다 확인. 단, 해당 원소로 만드는 스타수열의 길이가 이전에 스타 수열의 가장 긴 값을 넘길 수 없으면 가지치기로 시간단축 
        answer = 0 
        if cnt<=max_ans: continue #가지치기, 해당원소의 빈도가 최대 길이보다 작으면 가지치기 
        lst = [0]*(cnt+1) #공통 원소를 기준으로 사이에 존재하는 원소의 갯수를 저장하는 리스트
        idx = 0
        for i in range(n): #공통 원소를 만나면 lst 인덱스 +1, 그렇지 않으면 현재 인덱스의 lst값 +1 
            if a[i] == num:
                idx += 1
            else:
                lst[idx] += 1

        for i in range(1, cnt+1):
            #a의 모든 공통 원소마다 짝꿍 가능한지 양 옆의 원소 갯수 살펴보기 
            if lst[i-1]>0: #앞쪽 원소 먼저 살펴보기, 짝꿍 있으면 answer +1 
                lst[i-1] -= 1
                answer += 1
                continue 
            if lst[i]>0: #앞쪽 원소와 짝꿍 불가능하면 뒷쪽 원소와 짝꿍 가능한지 살펴보기, 가능하면 answer +1
                lst[i] -= 1
                answer += 1
                continue 
                
        max_ans = max(max_ans, answer) #최댓값 갱신 
    
    return max_ans*2

 

 

리뷰

• 화려한 알고리즘이 아닌 완전 아이디어 문제인것 같다
• 어려워 보일수록 문제를 최대한 단순한 형태로 치환해서 생각하자.!