[백준] 17299 - 오등큰수 (G3)

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

17299번: 오등큰수

난이도가 조금 있는 스택문제

알고리즘 분류가 스택이라는 것만 알아내면

아이디어가 어렵다기 보다는 구현이 조금 복잡하다고 생각한다.

 

오등큰수를 결정하는 제일 큰 기준은 '숫자의 등장 횟수' 이다.

따라서 숫자의 등장횟수를 미리 다 저장해둔다.

 

주어진 수열의 왼쪽부터 차례대로 순회하면서 해당 숫자의 등장 횟수를 스택에 저장해나가다

스택의 가장 위에 있는 수의 등장횟수보다 더 많은 등장횟수를 가진  수가 나타나면

그 수가 오등큰수에서 말하는 '등장횟수가 자기보다 더 큰 수 중 수열의 가장 왼쪽에 있는 수' 이다.

 

이제 스택의 가장 위에 있는 수의 등장횟수가 현재 방문한 수의 등장 횟수보다 작은 동안 반복해서 스택 원소를 pop 하고,

정답 배열에서 pop한 숫자가 있던 인덱스 위치의 값을 현재 방문한 수로 만들면 된다.

그리고 다시 위 과정을 반복한다.

 

정답 배열 같은 경우는 미리 -1로 전부 초기화를 해둔다.

이렇게 해두면 위 과정을 다 반복하고 스택에 남아있는 값들에 대해서는

정답배열에서 따로 조치를 할 필요가 없게 된다.

이 값들이 스택에 남아있다는 것은 이 값이 주어진 수열에서 등장횟수가 가장 큰 값이라 오등큰수가 없기 때문이다.

 

n = int(input())
count = {}
l = list(map(int, input().split()))
for i in range(n):
    v = l[i]
    try:
        count[v] += 1
    except:
        count[v] = 1
ans = [-1 for _ in range(n)]
stack = []

for i in range(n):
    v = l[i]
    while stack and stack[-1][0] < count[v]:
        pop_count, pop_value, pop_idx = stack.pop()
        ans[pop_idx] = v
    stack.append((count[v], l[i], i))

print(*ans)