[백준] 오큰수(17298) - Python

문제링크

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

문제이해

크기가 N인 수열 A = A1, A2, ..., AN이 있다. 수열의 각 원소 Ai에 대해서 오큰수 NGE(i)를 구하려고 한다. Ai의 오큰수는 오른쪽에 있으면서 Ai보다 큰 수 중에서 가장 왼쪽에 있는 수를 의미한다. 그러한 수가 없는 경우에 오큰수는 -1이다.

예를 들어, A = [3, 5, 2, 7]인 경우 NGE(1) = 5, NGE(2) = 7, NGE(3) = 7, NGE(4) = -1이다. A = [9, 5, 4, 8]인 경우에는 NGE(1) = -1, NGE(2) = 8, NGE(3) = 8, NGE(4) = -1이다.

입력

첫째 줄에 수열 A의 크기 N (1 ≤ N ≤ 1,000,000)이 주어진다. 둘째 줄에 수열 A의 원소 A1, A2, ..., AN (1 ≤ Ai ≤ 1,000,000)이 주어진다.

출력

 

총 N개의 수 NGE(1), NGE(2), ..., NGE(N)을 공백으로 구분해 출력한다.

 

이 문제를 직관적으로 해석하다가 시간초과를 접했다.

스택에 넣고 해당 값을 어떻게 인덱스마다 넣어주다가 지난번에 풀었던 탑 문제가 생각났고 이를 적용하니 쉽게 풀렸다.

*탑 문제 링크

https://chanjin98.tistory.com/75

[baekjoon] 탑(2493) - Python

answer 배열을 -1로 채워준다.(값이 없을 경우 -1이기 때문에)

stack에 값이 없다면 넣어주고 값이 있다면 스택의 마지막 값이랑 비교한다.

비교했을 때 현재 있는 값이 스택의 마지막값보다 크다면 스택의 들어있는 인덱스의 자리에 현재 값을 채워 넣고

다시 while 문을 돌리고 값이 크다면 같은 방법, 작다면 while문을 나가서 현재 값도 stack에 넣어주는 방식이다.

코드

import sys
from collections import deque

N = int(sys.stdin.readline())
A = list(map(int,sys.stdin.readline().split()))
answer = [-1 for _ in range(N)]
stack = []
for i in range(N):
  while stack and A[i] > stack[-1][1]:
    index, value = stack.pop()
    answer[index] = A[i]

  stack.append((i,A[i]))
print(*answer)