[백준 알고리즘/Python3] 17299 오등큰수

문제 이해

저번에 푼 오큰수와 비슷한 양상일거라 생각했습니다. 좀 더 복잡하게 생각해봤는데... 

스택에 값을 넣습니다. 스택에 값을 넣는 기준은

• 바로 전에 들어간 수(스택에 있는 수)가 다른 값이어야 합니다.
• 같은 값이면 그냥 스택에 넣습니다.
• 하나 넣을 때마다 스택에 같은 값이 있는지 확인합니다.
• 만약 같은 값이 있다면 값에 있는 인덱스까지 현재 값을 넣습니다.

이렇게 하니 틀렸다고 나왔습니다. 너무 오래 걸린 거 같습니다. 그래서 다른 풀이를 찾아봤습니다.

 

코드

from collections import Counter
list_size = int(input())

list = list(map(int,input().split()))

#수열들의 등장 횟수 체크
count = Counter(list)

stack = []

for i in range(list_size): # 수열의 크기만큼 

    #처음에 스택이 비어있다면 하나 넣고 시작
    if(stack == []):
        stack.append(i)
        continue

    #왼쪽 값의 등장 횟수가 오른쪽 보다 작으면 
    while(stack != [] and count[list[stack[-1]]] < count[list[i]] ):
        #왼쪽 값의 오등큰수는 오른쪽 값이다.
        list[stack.pop()] = list[i]

    stack.append(i)

while(stack != []):
    list[stack.pop()] = -1

#list의 int를 str로 변환
for z in range(len(list)):
    list[z] = str(list[z])

print(' '.join(list))

처음에 Counter라는 라이브러리를 찾아볼 생각을 못했습니다. 수열의 등장 횟수를 쉽게 파악할 수 있게 해 주었습니다.

수열들의 등장 횟수를 count에 두고 

• stack의 마지막 값(바로 왼쪽 값)과 지금 들어온 값의 등장 횟수를 비교해서 왼쪽 값의 등장 횟수가 더 적으면 
• 등장 횟수가 큰 왼쪽 값이 나올 때까지 pop을 해서 해당 인덱스에 값을 현재 값으로 변화시켜 줍니다.