BJ17298_오큰수_python

1. 문제링크

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

2. 풀이 전 계획과 생각

< 정보 정리 >

1) 입력값: 테스트 케이스 T, 정수 T개
2) 출력값: 각 정수의 오큰수
3) 제약조건:

- 1 <= T <= 1,000,000
- 1 <= 정수 <= 1,000,000

4) 예외케이스: 없음

< 공통 로직 >

• 현재 수(x)가 스택 마지막 값(인덱스)의 수(num[i])보다 클 경우, 해당 인덱스 위치에 있는 수(num[i])의 오큰수는 x다.

3. 풀이

def nge():
  n = int(input())
  num_list = list(map(int, input().split()))
  result = [-1 for _ in range(n)]
  stack = []
  stack.append(0)
  for i in range(n):
      while stack and num_list[stack[-1]] < num_list[i]:
          result[stack[-1]] = num_list[i]
          stack.pop()
      stack.append(i)
  for i in result:
    print(i, end = ' ')

nge()

4. 풀이하면서 막혔던 점과 고민

실제 값이 아닌 인덱스 값을 스택에 넣으면서 풀어야 하는 부분이 어려웠다.

5. 풀이 후 알게된 개념과 소감

처음에는 스택이 아닌 double for-loop를 사용했는데 그렇게 푸는 경우 대부분 시간초과가 난다는 것을 배웠다.