[알고리즘] 백준 17298번 Python

 

분류

스택

혼자 힘으로 해결 했는가?

O

느낀 점

앞서 2493번을 통해 monotone 스택 문제에 대한 감을 잡은 뒤 도전했다.

등급은 골드4로 2493보다 한단계 더 높지만 둘 다 난이도가 똑같이 느껴졌다.

 

다만 이 문제는 2493과 달리 검사의 대상이 되는 숫자가 담긴 배열의 역순으로 진행을 해야했다.

 

아마 현재 값의 우측 값에 관심이 있기 때문에 우측부터 시작해서 

현재 값을 기준으로 선행 된 값 중 나보다 큰 값이 처음으로 나오는가?

이렇게 문제를 해결하기 때문인 것 같다.

 

그리고 이 문제에서 중요한 키워드는 현재 값을 기준으로 오른쪽 값 중에서 가장 왼쪽에 있는 큰 값 이라고 생각한다.

 

위의 말을 다시 풀어서 쓰면 나보다 우측에 있는 값 중에 처음으로 발견되는 큰 값

 

따라서 스택을 써서 처음으로 나보다 큰 값이 발견되면 멈추면 된다.

 

만약 두번째로 발견되는 값이었다면 임시 저장소에 발견된 큰 값을 넣어두고 다시 스택을 복원해야 했을 것 같다.위 처럼 응용된 문제를 만나게 될 경우 이번 17298번 문제가 떠오르면 좋겠다.

---

 

내가 작성한 코드

 

정답을 받음

 

import sys
from collections import deque

N = int(input())

nums = list(map(int, sys.stdin.readline().rstrip().split()))

stack = deque()

ans = []

for i in range(N-1, -1, - 1):
    # 단조 증가이기 때문에 우측에서 시작해서 스택에 채워나간다.
    # 현재의 값보다 우측에 관심이 있기 때문임

    # 단조 증가, monotone stack
    # 가장 왼쪽, 즉 처음으로 발견되는 숫자 외에는 관심이 없다.
    # 스택에서 나보다 작은 숫자는 전부 빼버린다.


    # 스택이 빈 경우 예외 처리
    if not stack:
        ans.append(-1)
        stack.append(nums[i])

    # 스택을 비울 때 스택이 비거나 그만 비워야 할 때 까지만 비운다
    # 그만 비워야 하는지를 알기 위한 flag 설정

    flag = False
    while stack and not flag:

        if stack[-1] <= nums[i]:
            stack.pop()
        else:
            flag = True
            ans.append(stack[-1])
            stack.append(nums[i])

    # 만약 스택이 비기 전에 못 찾았다면 스스로를 스택에 담는다
    if not flag:
        stack.append(nums[i])
        ans.append(-1)

for i in range(len(ans) -1 ,0, -1):
    print(ans[i], end=" ")

 

---

비슷한 문제들

 

백준 2493번

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

2493번: 탑

 

백준 6198번

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

6198번: 옥상 정원 꾸미기