[백준] 17299 - 오등큰수

1. 문제

17299번: 오등큰수

2. 개요

수열이 주어졌을 때, 각 원소에 대해 그 원소보다 오른쪽에 있으면서 등장 횟수가 많은 원소를 구하는 스택 활용문제.

3. 코드 및 추가내용

import sys

N = int(sys.stdin.readline())
nums = list(map(int, sys.stdin.readline().split()))
nd = dict()
stk = []
ans = [-1 for _ in range(N)]

for i in range(N):
    if nums[i] in nd: nd[nums[i]] += 1
    else: nd[nums[i]] = 1

for i in range(N):
    if len(stk) == 0:
        stk.append([nums[i], nd[nums[i]], i])

    elif stk[-1][1] >= nd[nums[i]]:
        stk.append([nums[i], nd[nums[i]], i])

    else: 
        while stk and stk[-1][1] < nd[nums[i]]:
            ans[stk.pop()[2]] = nums[i]

        stk.append([nums[i], nd[nums[i]], i])

print(*ans)

결과 리스트의 초기값들을 1로 만들고, 딕셔너리로 각 원소의 등장횟수를 구해놓는다.

왼쪽 원소부터 다음 원소보다 등장횟수가 많다면 스택에 넣으며 진행한다.

스택 마지막 원소보다 등장횟수가 더 많은 원소가 나왔다면, 이 원소보다 등장횟수가 많은 원소를 찾아낼때까지 스택에서 원소들을 뽑아낸다. 뽑아낸 원소에 해당하는 정답 인덱스의 값을 해당 원소의 값으로 갱신한다. while문이 종료되었다면 마찬가지로 스택에 해당 원소를 집어넣는다.

모든 원소를 확인했다면 결과를 출력한다.