[백준 17299] 오등큰수 (python)

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

17299번: 오등큰수

오등큰수 문제

A의 오등큰수는 오른쪽에 있으면서 수열에서 등장한 횟수가 A보다 큰 수중에서 가장 왼쪽에 있는 수로 알 수 있는데, 이때의 오등큰수 리스트를 출력하는 문제

스택을 활용하는 문제인데, 쉬운듯 하면서 생각해내는게 어려운 문제였다.

정답 코드

import sys
N = int(sys.stdin.readline())
x = list(map(int, sys.stdin.readline().split()))
temp = [0]*100
stack = []
result = [-1 for _ in range(N)]

for k in x: 
    temp[k] += 1

for i in range(N):
    while stack and temp[x[stack[-1]]] < temp[x[i]]: #오등 큰수 조건
        result[stack.pop()] = x[i]
    stack.append(i)
print(*result)

먼저 오등큰수는 존재하지 않을 경우 -1로 할당해야 하므로 먼저 -1로 N개만큼 result로 만들어주고, 여기서 오등큰수가 존재 하면 해당 인덱스의 값을 바꾸는 식으로 구성해주었다.

일단 수열의 값을 인덱스로해서 temp에 갯수를 저장해주고, 스택이 존재할 동안 스텍의 마지막숫자를 인덱스에 해당하는 x의 요소를 다시 인덱스로 해당하는 temp가 다음 인덱스보다 크면 그때의 수를 result에 저장하는 형태로 만들었다.

코드를 말로 풀어쓰니 어려운거지, 오등큰수의 정의 그대로를 코드로 짜준거 뿐이다.

이걸 코드로 구현하는게 생각보다 헷갈려서 쉽게 만들지 못해서 아쉬웠던 문제였다.

---

느낀점

스택에 대해 더 공부하고자 풀어본 문제였다. 생각보다 간단하면서도 아이디어가 쉽사리 떠오르지 않았는데, 사실 문제의 정의 그대로를 코드로 구현하면 성공할 수 있는 문제였다.

하지만 생각보다 쉽게 하지 못했던 점에서 구현능력이 많이 부족함을 느꼈었다. 구현 능력을 기르기 위해서 당분간은 백준의 여러 구현 문제를 시도해볼 필요가 있다는걸 요즘 계속해서 느끼고있다.