[백준] 17298 오큰수

1. 문제

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

17298번: 오큰수

 

 

2. 풀이

 

사실 이문제는 열심히 풀었는데 계속 시간초과가 났다ㅠ 그래서 도움을 좀 받은,,,

 

그래도 덕분에 스택을 잘 사용하는 법을 알게됨.

 

처음엔 그냥

 

원래 스택 -> 이미 사용한 스택 이렇게 해서 다 검사하게 했는데

생각해보니 뒤에 보낼때 다~~ 검사하는게 아니라 한번이라도 어떤 수보다 작았으면 pop 하면 됐는데ㅠ 그걸몰랐다.

 

1) NGE, stack 변수를 설정한다.

2) i=n-1부터 돌면서 뒤에서부터 pop 하는 식으로 간다.

3) stack이 빌 경우, stack에 현재 index를 추가한다.

4) 이후 stack이 차있는데, 현재값보다 stack[-1]의 값이 더 작으면 stack을 pop하고 큰게 나올때까지 pop한다.

5) 끝까지 나오지 않으면 끝내고 stack에 다시 append하고, 오큰수를 찾으면 NGE를 stack[-1]로 업데이트 해준다.

Flow 설명

 

## code ##

import sys

n = int(sys.stdin.readline())
nums = list(map(int, sys.stdin.readline().split()))
NGE = [-1] * n  # 초기에 모든 원소를 -1로 초기화
stack = []

for i in range(n-1, -1, -1):
    while stack and nums[i] >= nums[stack[-1]]:
        stack.pop()
    if stack:
        NGE[i] = nums[stack[-1]]
    stack.append(i)

print(*NGE)