Level 3 스타 수열 Python 3

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

코딩테스트 연습 - 스타 수열

 

최종 코드

• GitHub -> https://github.com/hwayeon351/Programmers-Algorithms/blob/main/level3_스타수열.py

GitHub - hwayeon351/Programmers-Algorithms: 프로그래머스 알고리즘 소스 코드 모음

from collections import Counter
def solution(a):
    answer = -1
    num_dict = Counter(a).most_common()
    for key, value in num_dict:
        if answer > 2*value: continue
        i = 0
        cnt = 0
        while i < len(a)-1 and cnt < 2*value:
            if a[i] == key:
                if a[i+1] != key:
                    cnt += 2
                    i += 2
                else:
                    i += 1
            else:
                if a[i+1] == key:
                    cnt += 2
                    i += 2
                else:
                    i += 1
        if cnt > answer: answer = cnt
    return answer

---

풀이 과정

 수열 x의 부분 수열 중 가장 길이기 간 스타 수열의 길이를 구하는 문제이다.

스타 수열은 다음과 같은 조건을 만족해야 한다.

1. 수열의 길이가 2이상의 짝수이다.

2. 앞에서 부터 2개씩 집합을 만들었을 때, 모든 집합의 교집합의 원소는 1개 이상이어야한다.

3. 각 집합의 원소들 끼리는 서로 달라야 한다.

 

즉, 2번의 조건에서 모든 집합에 공통된 원소가 최소 1개씩은 포함해야 하기 때문에, 파이썬 딕셔너리 Counter를 사용하여 수열 x에 들어간 원소의 종류별 개수를 구해준다.

그 후 해당 종류의 개수 x 2만큼이 최대 예상 가능한 스타 수열의 길이가 될 수 있기 때문에, 가장 많은 개수 순서대로 해당 원소를 하나씩 가진 집합들로 구성된 스타 수열을 만든다.

만들어진 스타 수열의 길이를 비교하여 최대 길이를 갱신해 나간다.

 

from collections import Counter
def solution(a):
    answer = -1
    #수열 a의 각 원소의 개수를 많은 순서대로 정렬
    num_dict = Counter(a).most_common()
    #key = 원소, value = 원소의 개수
    for key, value in num_dict:
    	#이전에 구한 스타수열의 최대 길이가 해당 원소를 사용하여 만들 수 있는 최대 길이보다 큰 경우, 다음 원소로 넘어간다.
        if answer > 2*value: continue
        
        #스타수열 만들기
        i = 0
        cnt = 0
        while i < len(a)-1 and cnt < 2*value:
        	#현재 가리키는 원소가 key값인 경우,
            if a[i] == key:
            	#다음 가리키는 원소가 key값이 아니어야 하나의 집합을 이룬다
                if a[i+1] != key:
                    cnt += 2
                    i += 2
                #다음 가리키는 원소도 key값인 경우, 현재 원소는 제거한다
                else:
                    i += 1
            #현재 가리키는 원소가 key값이 아닌 경우,
            else:
            	#다음 가리키는 원소가 key값이어야 하나의 집합을 이룬다
                if a[i+1] == key:
                    cnt += 2
                    i += 2
                #다음 가리키는 원소가 key값이 아닌 경우, 현재 원소는 제거한다
                else:
                    i += 1
        if cnt > answer: answer = cnt
    return answer
#시간복잡도 = O(n^2), 공간복잡도 = O(n)

---

오답 노트

 처음에 문제 접근을 할 때, 수열 a의 모든 부분 수열을 만들어서 해당 수열이 스타 수열인지 판별해 나가는 방식으로 풀어보았다.

결과는 초반 몇 개는 맞고, 나머지는 시간 초과와 실패가 나왔다.

풀었던 코드를 다시 천천히 되짚어 봤는데도 불구하고 실패는 왜 나왔는지 알 수 없었다.

하지만 모든 경우의 수를 구해서 스타 수열인지 아닌지 판별해 나가는 방식은 시간이 많이 소요되어 다르게 접근해야할 필요를 느꼈다.

문제에 접근할 때 여러 방식으로 생각해보고 적용해보는 연습이 필요할 것 같다.

import sys
from collections import defaultdict
sys.setrecursionlimit(1000000)
def make_sub(idx, cnt, aa, na, target, visit):
    global answer
    if answer == target: return
    if cnt==target:
        v = "".join(map(str,na))
        if visit[v] == 1: return
        visit[v] = 1
        if na[0] == na[1]: return
        ck = [na[0], na[1]]
        for i in range(2, target, 2):
            if na[i] == na[i+1]: return
            if na[i] in ck or na[i+1] in ck: continue
            return
        answer = target
        return
    for i in range(idx+1, len(aa)):
        na.append(aa[i])
        make_sub(i, cnt+1, aa, na, target, visit)
        na.pop()
        
def solution(a):
    global answer
    if len(a) == 1: return 0
    answer = 0
    cnt = len(a)
    visit = defaultdict(int)
    if len(a)%2 == 1: cnt -= 1
    while cnt >= 2:
        aa = a[:]
        na = []
        make_sub(-1, 0, aa, na, cnt, visit)
        if answer > 0: return answer
        cnt -= 2
    return answer