[백준] 17298 파이썬(python) : 오큰수 - (monotone stack 알고리즘)

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

17298번: 오큰수

 

 

from collections import deque
n = int(input())
arr = list(map(int, input().split()))

answer = [-1]*n #1
stack = deque()

for i in range(n): #2
    while stack and (stack[-1][0] < arr[i]): #3
        tmp, idx = stack.pop() #4
        answer[idx] = arr[i] #5
    stack.append([arr[i], i]) #6
print(*answer) #7

 

#1 : 마지막 값은 항상 -1이 나오기 때문에 0이 아닌 -1로 지정

#2 : 인덱스와 일치시키기 위해서 range(n)

#3 : stack이 비어있지 않고 stack의 가장 끝값의 첫번째 요소(tmp)가 비교하는 리스트의 값보다 작을때 (오른쪽에 있으면서 큰 수중 가장 왼쪽의 수)

#4 : 값과 인덱스 pop()

#5 : 오큰수 갱신

#6 : stack이 비어있는 맨처음이거나 리스트이 값이 stack끝값보다 클때 이용

#7 : 리스트 unpacking 후 출력

 

O(n^2) 복잡도가 나오는 문제를 시간제한 때문에 O(n)복잡도로 풀어야 하는 문제. 이해하기 힘들었다.

"달팽이는 올라가고 싶다"와 비슷한 느낌의 문제인데 이런류의 문제도 많이 풀어봐야 할것 같다.

 

다른풀이) 22.7.23

monotone stack 알고리즘을 배웠다. 비슷한 문제도 풀어보고 이 문제도 같은 알고리즘으로 풀 수 있다해서 몇가지 추가하겠다.

 

import sys
n = int(sys.stdin.readline())
number = list(map(int, sys.stdin.readline().split()))
res, stack = [-1]*n, [] #1
for i in range(n):
    while stack and number[stack[-1]] < number[i]: #2
        res[stack.pop()] = number[i] #3
    stack.append(i) #4
print(*res)

 

#1 : 오큰수를 찾을 수 없는 경우는 -1을 출력해야 하므로 -1로 모두 초기화

#2 : 단조 스택 알고리즘의 중복없는 내림차순 유지

#3 : stack에 있는 원소가 값이 아닌 인덱스이기 때문에 stack.pop()으로 원하는 위치에 값 지정 가능

#4 : 인덱스를 삽입

 

---

2493번 : 탑

 

2812번 : 크게 만들기