[백준] 17299 오등큰수 [Python, 파이썬]

• 문제 : https://www.acmicpc.net/problem/17299
• 🔑 스택, 입력받은 숫자 리스트 역순으로 순회
  • 먼저 입력받은 숫자들의 개수를 센다.
    • 리스트 순회하면서 count() 함수로 셀 수도 있지만
    • collections 모듈의 Counter 클래스로 간단하게 셀 수 있다.
    •  
  • 리스트의 값을 역순으로 스택에 넣는 이유
    • 스택에 현재 들어온 숫자의 바로 밑에 있는 숫자가 현재 들어온 숫자의 개수보다 많은 것 중 가장 왼쪽의 값으로 만들기 위함

 

from collections import Counter

n = int(input())

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

cnt = Counter(numbers)      # 숫자의 개수 세기

stack = []
answer = [0] * n

for i in range(n-1, -1, -1):        # 리스트 역순으로 순회 
    if not stack:                   # 스택 비어있으면
        stack.append(numbers[i])    # 스택에 추가
        answer[i] = -1              # 정답에 -1 추가
    elif cnt[stack[-1]] > cnt[numbers[i]]:  # 스택 맨 위 숫자의 개수가 현재 들어오는 숫자의 개수보다 많으면
        answer[i] = stack[-1]               # 정답에 스택 맨 위 숫자 추가
        stack.append(numbers[i])            # 스택에 현재 숫자 추가
    else:
        while stack and cnt[stack[-1]] <= cnt[numbers[i]]:  # 스택에 값이 있고, 
                                                            # 스택 맨 위 숫자의 개수가 현재 들어오는 숫자의 개수보다 작거나 같으면 
            stack.pop()                                     # 스택에서 뺀다
        if not stack:                                       # 다 빼고 스택이 비어있으면 
            answer[i] = -1                                  # 정답에 -1 추가
            stack.append(numbers[i])                        # 스택에 현재 숫자 추가
        else:                                               # 스택에 값이 남아있으면
            answer[i] = stack[-1]                           # 정답에 스택 맨 위 숫자 추가
            stack.append(numbers[i])                        # 스택에 현재 숫자 추가

print(*answer)