[Python] BOJ 17298 : 오큰수

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

생각 중

• 스택이 비어 있을 때, 인덱스를 넣어줘 전 값을 저장하자.
• 스택이 비어 있지 않을 때, 저장된 인덱스 값의  NGE[index] 와 다음 값인 NGE[i]를 비교하자.
  • 만약 NGE[i] 가 더 크다면 stack을 pop하고 result[index] 에 NGE[i] 값을 넣어주자. 

요구사항

• 시간 제한 1초 N <= 1,000,000 
  • 보자마자 아 2중 for문은 안되겠구나. 
• 메모리 제한 512MB 
• 특정 원소 보다 오른쪽에 있으면서 가장 큰 수 중에 가장 왼쪽에 있는 수를 구하는 프로그램을 만들 것. 

설계 

• 수열의 크기 N 을 입력 받는다. 
• 사용자로 부터 수열을 입력 받는다.
• 결과를 저장할 리스트를 초기화 한다. [-1] * N 
• stack = []  : index 를 저장할 것이다.
• 수열의 크기 동안 반복되는 for문을 만든다. 
• while stack and NGE[stack[-1]] < NGE[i] 일 때
  • index = stack.pop()
  • result[stack] = NGE[i]
• stack.append(i) : stack이 비어 있을 때 넣을 것. 
• print(map(str, result))
  • int 로 하지 않음 주의. 

구현

import sys
input = lambda: sys.stdin.readline().rstrip()

N = int(input())
NGE = list(map(int, input().split()))
result = [-1] * N
stack = []

for i in range(N):
    while stack and NGE[stack[-1]] < NGE[i]:
        index = stack.pop()
        result[index] = NGE[i]
    stack.append(i)

print(" ".join(map(str, result)))