[백준] 17298번 : 오큰수 (python 파이썬)

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

17298번: 오큰수

 

 

 

 

 

문제 정리 : 배열의 각 수 마다 자신보다 오른쪽에 있으면서 자신보다 큰 수 중 가장 왼쪽에 있는 수 출력. 없는 경우 -1 출력.

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

import sys
from collections import deque

n = int(sys.stdin.readline())
l = list(map(int, sys.stdin.readline().rstrip().split(" ")))

d = deque(l)
ans = [-1 for i in range(n)] # 답 선언 (-1인 이유는 답이 없는 경우 -1로 처리해야 하기 때문)
stack = []

for i in range(len(l)): # i 는 스택의 인데스를 의미

    a = d.popleft() # 덱의 왼쪽 값 추출 및 제거 
    while stack and a > stack[-1][0]:  # 스텍 안에 요소가 존재하고, 스택의 마지막 원소의 우큰수가 a인 경우
        ans[stack[-1][1]] = a # 답의 인덱스에 우큰 수 넣기 (stack[-1][1] = 인덱스)
        stack.pop() # 사용된 우큰수 제거
    stack.append([a,i]) # 스텍에 덱의 왼쪽 값과 인덱스 입력
    
    
print(*ans) # unpackage 리스트를 str으로 출력

 

 

 

 

 

 

 

 

 

 

우선 입력 받는 문자을 공백을 기준으로 나눠 리스트 l에 담는다.

그 후 리스트 l을 덱으로 바꾼다.

for문을 돌면서 덱에서 왼쪽값을 하나씩 빼면서 stack에 값과 인덱스 값을 넣는다.

for문에서 왼쪽 값을 뺄 때, 뺀 값이 stack안의 마지막 원소보다 크면, 뺀 값은 마지막 원소의 우큰수가 된다.

만약 우큰수가 존재한다면 stack에 입력된 값과 인덱스를 이용해서 ans를 수정한 후, stack에서 뺌으로서 제외시킨다.

stack안에 요소가 없거나 a가 마지막 원소의 우큰수가 아닐 때까지 반복한다.(while문)

 

처음에는 뒤집어서 순서를 반대로 하보려는 시도를 했지만 결국 같은 시간이 걸림.

따라서 핵심은 한번 확인했고, 이미 결정된 원소는 stack에서 제거하면서 연산 수를 줄임으로서

시간 복잡도를 줄일 수 있다.