[백준] 17299번 : 오등큰수

17299번: 오등큰수

17299번: 오등큰수

🤔 문제분석

스택 자료구조를 활용하면 문제를 해결 할 수 있다. counter 해당 숫자의 개수를 누적하고, 인덱스로 접근하여 개수의 크기를 판별한다. 만약 리터리에션에서 자기자신보다 작은 counter들은 모두 꺼내고, 작업을 다완료한뒤 stack의 크기를 확인하여 stack이 0보다 크면 스택의 마지막 원소에서 인덱스를 가져오고 그렇지 않다면 -1을 넣는다.

💻 코드

import sys
input = sys.stdin.readline

N = int(input())
data = list(map(int, input().split()))
counter = [0 for _ in range(1000001)]

for i in range(N):
    counter[data[i]] += 1

stack = []
result = []
for i in range(N-1, -1, -1):
    while stack and stack[-1][0] <= counter[data[i]]:
        stack.pop()
        
    if stack and stack[-1][0] > counter[data[i]]:
        result.append(stack[-1][1])
    else:
        result.append(-1)
        
    stack.append((counter[data[i]], data[i]))

print(' '.join(map(str, reversed(result))))

🎯 피드백 및 개선사항

그리디한 방식으로 접근하면 어렵지 않게 풀을 수 있는 문제였습니다. 자기자신보다 작은 counter들은 모두 pop하면서 자기신보다 크면서 가장 왼쪽에 있는 인덱스를 찾을 수 있습니다.