[BOJ] 17298번 - 오큰수

---

문제설명

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

17298번: 오큰수

사고과정

• 처음에 이중 for 문으로 구현하려 했다가 바로 시간초과가 발생하는 것을 인지했다.. 그래서 어떻게든 자료구조 스택이나 큐를 활용해서 해결해야 할 것 같은데.. 큐를 활용해보려고 했으나 큐도 어쨌거나 한 번의 선형 루프를 또 활용하는 아이디어 밖에 떠오르지 않았다.. 스택은 어떻게 활용할지 감이 오지 않았다
• 풀이를 보니 스택을 활용했는데, n개의 수열 하나씩 도는데, 안에다가 while 문과 스택을 활용해서 해결했다.
• answer이라는 각 수열의 인덱스에 해당하는 오큰수 값으로 하고 -1로 해서 초기화시켰다(-1로 초기화시켜서 오큰수가 없는 수는 자동으로 -1을 출력할 수 있도록 했음)
• 스택에는 원소값이 아닌 수열의 인덱스를 넣어준다. 그리고 수열의 가장 첫번째 인덱스를 스택에 넣고 시작한다. 그리고 수열의 인덱스를 1부터 n-1까지 돌면서 현재 수열의 값 >  스택의 마지막 인덱스가 가리키는 수열의 값 이게 되면 오큰수에 해당하는 조건이므로 answer 리스트에 업데이트 해준다. 단, 가장 왼쪽에 있는 값을 가져와야 하므로 while문으로 스택에 가장 앞에 있는 원소까지 반복할 수 있도록 했다..
• 간단한 문제인 줄 알았는데 스택을 매우 잘 활용해야 하는 문제인 듯 하다..

풀이(스스로 못 푼 풀이)

import sys

input = sys.stdin.readline
n = int(input().rstrip())
array = list(map(int, input().split()))
answer = [-1] * n
stack = []
stack.append(0)

for i in range(1, n):
    # 스택의 FILO 순서로 하나씩 빼면서 대소비교 -> 스택의 왼쪽으로 가면서 '가장 왼쪽에 있는 수'를 탐색!
    while stack and array[i] > array[stack[-1]]:
        answer[stack.pop()] = array[i]
    stack.append(i)

print(*answer)