[백준] 17299번 - 오등큰수 (파이썬)

https://www.acmicpc.net/problem/17299

# 오등큰수
from collections import Counter
import sys
input = sys.stdin.readline

N = int(input())
arr = list(map(int, input().split()))
count = Counter(arr)
result = [-1] * N
stack = []

for i in range(N):
    while stack and count[arr[stack[-1]]] < count[arr[i]]:
        result[stack.pop()] = arr[i]
    stack.append(i)

print(*result)

 

자료구조(스택)

1. Count를 이용해서 개수 딕셔너리를 만든다.

2. 반복문 시작

    - 현재 인덱스(stack [-1])의 값보다 i의 값이 더 작으면 전부 pop (pop한 인덱스의 답 :  현재 값)

    - 이후 스택에 i appepnd

3. result 출력

 

stack의 count값이 항상 오름차순으로 정렬된 상태를 유지 하겠다고 생각하면 쉽다

블로그 시작하기 전에 정말 똑같은 문제를 풀었어서 그 문제도 블로그에 올리고 이 문제를 올린다

 

[백준] 17298번 오큰수

[백준] 17298번 - 오큰수 (파이썬)