BOJ 17298 오큰수

재재

안녕하세요,
재재입니다.

BOJ 17298 오큰수 문제 풀이입니다.

BOJ 17298 오큰수

(1) 문제 설명

분류 : 구현, 자료구조, stack

출처 : https://www.acmicpc.net/problem/17298

(1,000,000 이하) N 개의 숫자가 주어집니다.
각 숫자에 대해 오른쪽에 있으면서, 큰 숫자 중 가장 왼쪽에 있는 숫자를 출력해주면 됩니다.

(2) 풀이 도출

현재 숫자보다 한 단계 큰 숫자를 찾으면 됩니다.

임의의 자료구조를 사용해서 현재 숫자보다 작으면 넣고,
현재 있는 숫자보다 크면 해당 값을 기록하면 됩니다.
이때, 이 자료구조는 stack 을 사용해도 충분하다는 것을 알게 됩니다.

좀 더 구체화하면,

1. stack 이 비어있거나 새로 들어갈 숫자가 작은 경우 push
2. stack 의 top 보다 현재 숫자가 큰 경우 pop 하면서,
   해당 값을 기록해야합니다. (반복 가능)

기록될 모든 값에 -1을 입력하고,
-1 인 경우에만 값을 기록한다면 이 문제를 쉽게 풀 수 있습니다.

(3) 정답 코드