문제: https://www.acmicpc.net/problem/17299
-> 히스토그램 문제의 기초문제
스택으로 푸는 문제
풀이
import sys
input = sys.stdin.readline
from collections import Counter
n = int(input())
aa = list(map(int,input().split()))
ff = Counter(aa)
stack = []
ngf = [-1] * n
for i in range(n):
while stack and ff[aa[stack[-1]]] < ff[aa[i]]:
ngf[stack.pop()] = aa[i]
stack.append(i)
print(*ngf)
input
7
1 1 2 3 4 2 1
스택 변화
[0]
[0, 1]
[0, 1, 2]
[0, 1, 2, 3]
[0, 1, 2, 3, 4]
[0, 1, 2, 3]
[0, 1, 2]
[0, 1, 2, 5]
[0, 1, 2]
[0, 1]
[0, 1, 6]
#ngf변화
[-1,-1,-1,-1,-1,-1,-1]
[-1,-1,-1,-1,2,-1,-1]
[-1,-1,-1,2,2,-1,-1]
[-1,-1,-1,2,2,1,-1]
[-1,-1,1,2,2,1,-1]