[백준 17298] 오큰수 (python)

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

17298번: 오큰수

오큰수 문제

A[i]의 오른쪽에 있으면서 A[i]보다 큰 수 중에서 가장 왼쪽에 있는 수인 오큰수를 구하는 문제

스택을 이용하여 해결할 수 있었다.

📌문제 접근 포인트

1. 오큰수를 저장할 리스트를 먼저 만들어주자. 요구 조건에 오큰수가 없을 경우 -1로 표시해야하니 [-1] * N 사이즈의 리스트를 만들어주자.
2. 스택과 해당 A[i]의 인덱스를 사용해보자. 오큰수는 오른쪽에 있으면서 A[i]보다 큰 수 중 가장 왼쪽 값을 구해야 하므로, 후입선출 자료 구조인 스택을 활용하면 유리하다. 먼저 스택에 첫 값에 해당하는 0번 인덱스를 저장하고, 그 뒤 숫자에 대해서 스택을 활용하여 탐색해보자.
3. 스택에 들어간 마지막 인덱스와 현재 A[i] 중에 A[i]가 더 큰 요소라면 그 인덱스는 오큰수에 해당하므로, 스택에서 제거해주면서 A[i]로 값을 설정해주자.
4. 반복적으로 탐색하도록 구현하면 성공

반응형

⚙ 내가 푼 정답 코드

import sys
N = int(sys.stdin.readline())
A = list(map(int, sys.stdin.readline().split()))
NGE= [-1]*N
stack = [0] # 0번 인덱스

for i in range(1, N):
    # 오큰수 : A[i]의 오른쪽에 있으면서 A[i]보다 큰 수 중 가장 왼쪽 값 
    while stack and A[stack[-1]] < A[i]:
        NGE[stack.pop()] = A[i] # 해당 인덱스 칸은 A[i]
    stack.append(i)
print(*NGE)