[BOJ/Python] 17298. 오큰수

📌 문제

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

17298번: 오큰수

 

📌 문제 접근 방법

• 스택을 활용해서 풀이해보았다.
• 오큰수가 존재하지 않으면 -1을 입력하기 때문에 answer의 초기값을 -1로 설정했다.
• 스택에 값을 넣고 스택에 들어있는 값보다 큰 값이 들어오면 그 값보다 작은 값을 스택에서 모두 빼낸다.

예시로 수열 3 5 2 7 을 순회한다면,

1. i = 0 / 수열의 해당 값 = 3
   • 스택이 비어있으므로 3과 3의 인덱스를 각각 스택에 넣는다.
   • 현재 answer = [-1, -1, -1, -1]
     

     

2. i = 1 / 수열의 해당 값 = 5
   • 5는 3보다 크므로 각 스택에서 3과 0을 꺼낸 후, answer의 0번째에 5을 저장한다.
   • 현재 answer = [5, -1, -1, -1]
   • 그 후, 5와 5의 인덱스를 다시 스택에 넣는다.
     

     

3. i = 2 / 수열의 해당 값 = 2
   • 2는 5보다 작으므로 2와 2의 인덱스를 스택에 넣는다.
   • 현재 answer = [5, -1, -1, -1]
     

     

4. i = 3 / 수열의 해당 값 = 7
   • 7은 2보다 크므로 각 스택에서 2와 2을 꺼낸 후, answer의 2번째에 7을 저장한다.
   • 현재 answer = [5, -1, 7, -1]
     

     

   • 7은 5보다 크므로 각 스택에서 5와 1을 꺼낸 후, answer의 1번째에 7을 저장한다.
   • 현재 answer = [5, 7, 7, -1]
     

     

   • 코드 상, 7과 7의 인덱스도 비어있는 스택에 들어가게 되지만 수열의 순회가 끝났으므로 스택에서 빼서 answer에 저장하는 일은 발생하지 않는다.
     (어차피 7은 제일 오른쪽의 수라서 오큰수가 존재하지 않는다.)

 

📌 코드

import sys

N = int(sys.stdin.readline())
A = list(map(int, sys.stdin.readline().split()))   # 3 5 2 7

answer = [-1]*N
stack = []
idx_stack = []

i = 0

while i < N:
    if stack and stack[-1] < A[i]:
        stack.pop()
        answer[idx_stack.pop()] = A[i]
        continue
    else:
        stack.append(A[i])
        idx_stack.append(i)
    
    i += 1

print(*answer)