Study / Algorithma minute read (About 180 words)

백준 17299번 오등큰수


백준 17299번 오등큰수

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
import sys

num = int(input())
a = list(map(int, input().split(" ")))
result = ["-1" for _ in range(num)]
stack = [0]
count = dict()
for i in a:
    try:
        count[i] += 1
    except:
        count[i] = 1

for i in range(num):
    while stack and count[a[stack[-1]]] < count[a[i]]:
        result[stack[-1]] = str(a[i])
        stack.pop()
    stack.append(i)
    i+=1

print(" ".join(result))

[17298]오큰수와 같은 유형의 문제이다. 다만, 오등큰수는 각 원소 별 합에 대한 크기를 비교한다.

count에 원소를 키로 해서 키 별 원소 개수를 저장한다.

stack에는 a의 인덱스 값을 저장할 건데, for문을 돌면서 count[a] 값이 작은 a의 인덱스를 stack에 push하다가 stack[-1]보다 큰 count[a]를 만나면 stack에서 인덱스를 pop한다.

Comments

×