프로그래머스 [Lv. 3] 스타 수열 {언어 : Python}

문제 링크

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

프로그래머스

정답 코드

def solution(a):
    answer = 0
    aDict = dict()
    lenA = len(a)
    for i in range(lenA):
        if aDict.get(a[i], 0):
            aDict[a[i]].append(i)
        else:
            aDict[a[i]] = [i]
    aDictKeys = list(aDict.keys())
    for j in range(len(aDictKeys)):
        aKey = aDictKeys[j]
        arr = aDict[aKey]
        cnt = len(arr)
        stack = []
        for k in range(len(arr)):
            if stack:
                if stack[-1][1] == arr[k]:
                    stack.pop()
                    stack.append((arr[k], arr[k]+1))
                else:
                    # 하나 차이나면 뒤에꺼
                    # 두 개 이상 차이나면 앞에꺼
                    if stack[-1][1] + 1 == arr[k]:
                        if arr[k] + 1 == lenA:
                            break
                        else:
                            stack.append((arr[k], arr[k]+1))
                    else:
                        stack.append((arr[k]-1, arr[k]))
            else:
                if arr[k] == 0:
                    if arr[k] + 1 == lenA:
                        break
                    else:
                        stack.append((0, 1))
                elif 0 < arr[k]:
                    stack.append((arr[k]-1, arr[k]))
        if answer < len(stack) * 2:
            answer = len(stack) * 2
    return answer

풀이 방법

1. 교집합 원소를 딕셔너리의 key로 나누고 스택에 위치를 저장한다.
2. 해당 교집합 원소를 대상으로 얼마나 많이 부분 수열을 만들 수 있는지 확인한다.
3. 계산법은 다음과 같다.
   1. 만약 20이라는 교집합의 위치가 [1, 3, 4, 6] 이라면
   2. stack에는 (0, 1), (2, 3), (5, 6)이 들어간다.
   3. (4, 5)는 (5, 6)과 겹치기 때문에 stack에서 빠지게 된다.
   4. 결과적으로 3개의 부분수열 = 길이 = 3 * 2 = 6이 된다.
4. answer를 리턴하면 된다.

느낀점

• 어떻게 풀어야지는 떠올랐는데 제 시간 안에 푸는 연습이 필요하다고 느꼈다.