[백준] 17298번. 오큰수

[백준] 17298번. 오큰수 바로가기

아이디어

• monotone stack으로 스스로 푼 첫 문제 🤓
• 자신보다 큰 수 중에서 가장 가까이(왼쪽)에 있는 수를 찾는 것

1. 수열을 거꾸로 뒤집어서 검사한다
2. 첫 숫자는 비교 대상이 없기 때문에 stack에 담는다
3. 이후 현재 숫자와 stack의 마지막(top) 숫자를 비교해서 자신보다 클 때까지 pop한다.
4. 자신보다 큰 수가 나오면 result에 그 수를 담고 현재 숫자를 stack에 넣는다.
5. 3-4를 반복한다.
6. 자신보다 큰 수가 없으면 -1을 담는다.

stack	현재 숫자	수열	자신보다 큰 왼쪽수
[]	7	[3, 5, 2]	-1
[7]	2	[3, 5]	7
[7, 2]	5	[3]	7
[7, 5]	3	[]	5

시간 복잡도

• O(N)

코드

• deque으로 푼 코드

from collections import deque
import sys
input = sys.stdin.readline

n = int(input())
sequence = deque(map(int, input().split()))
stack = []
result = [] # 자신보다 큰 수 담는 리스트


while sequence:
    # 진행방향 거꾸로 검사한다
    number = sequence.pop()

    # 자기보다 같거나 작으면 stack에서 제거
    while stack and stack[-1] <= number:
        stack.pop()

    # 자기 보다 큰 수 중 제일 왼쪽(위쪽)에 있는 수 담기
    if stack:
        result.append(stack[-1])
    else:
        result.append(-1)
    stack.append(number)

result.reverse() # 다시 진행방향으로 바꿔주기

print(*result)

• [::-1]으로 푼 코드

from collections import deque
import sys
input = sys.stdin.readline

n = int(input())
sequence = list(map(int, input().split()))
stack = []
result = [] # 자신보다 큰 수 담는 리스트


# 진행방향 거꾸로 검사한다
for number in sequence[::-1]:
    # 자기보다 작으면 stack에서 제거
    while stack and stack[-1] <= number:
        stack.pop()

    # 자기 보다 큰 수 중 제일 왼쪽(위쪽)에 있는 수 담기
    if stack:
        result.append(stack[-1])
    else:
        result.append(-1)
    stack.append(number)

result.reverse() # 다시 진행방향으로 바꿔주기

print(*result)