[BOJ] 2493. 탑

문제

탑 (https://www.acmicpc.net/problem/2493)

풀이

1. 초기 접근

• 문제조건 해석
  • N 이 500,000만 이하로 주어진다고 한다. 즉 O(N) 또는 O(N log N) 안으로 풀어야 한다.
  • 선형 탐색 한 번만 가능한 것이다.
• 알고리즘
  • 주어진 예제 6 9 5 7 4 에서 앞의 인덱스부터 하나씩 탐색해나간다 했을 때, 현재 인덱스의 값의 올바른 정답이 무엇인지 차근차근 생각해보자.
  • 맨 왼쪽 6은 수신하는 곳이 없으니 항상 0일 것이다.
  • 9 도 마찬가지로, '지금까지' 9 보다 큰 값이 없었으므로, 값은 0이 된다.
  • 5 에서는, 지금까지5 보다 큰 값인 9가 있었다. 따라서 값은 배열에서 9의 인덱스값인 1이 된다.
  • 7도 마찬가지다. 지금까지 7보다 큰 값은 9였으므로, 이 역시 값이 1이 된다.
  • 4 에서 한 가지 알게될 수 있는 사실이 있는데, 지금까지 가장 큰 값은 9 였으나, 9의 인덱스 값이 아닌, 7 의 인덱스 값인 4가 정답이다.
  • 지금까지의 사실을 생각해보면, 우리는 '지금까지의' 큰 값들을 저장해나가야 한다.
    그럼 큰 값이라는건 언제 결정되는가? 현재 값과 비교함으로써 결정된다.
  • 큰 값들을 순차적으로 저장하고, 가장 마지막에 저장한 큰 값들과 현재 값을 비교한다는 점에서, 우리는 스택을 사용해야함을 알 수 있다.
• 코드

import sys
n = int(input())
arr = list(map(int, sys.stdin.readline().split()))
s, answer = [], []
for idx, height in enumerate(arr, 1):
    # 맨 처음 0번째 인덱스의 경우만 따로 처리
    if not s:
        s.append((idx, height))
        answer.append(0)
        continue

    # 현재 값 height 와, 스택에서의 top값의 height을 비교하여,
    # 스택에는 (인덱스, 큰 값) 들을 저장해둔다.
    # 1) 즉, 현재 값이 스택 top의 값보다 큰 경우,
    # 스택 top값이 현재값 보다 큰 경우일 때까지 계속해서 pop한 후, 현재 값을 넣어주는 것이다.
    # 2) 만약 현재 값이 스택 top의 값보다 작은 경우,
    # 스택 top에 저장된 인덱스값을 answer[idx]에 저장하면 된다.
    while s and s[-1][1] < height:
        s.pop()
    if s:
        answer.append(s[-1][0])
    else:
        answer.append(0)
    s.append((idx, height))
print(*answer)

2. 최소 힙을 이용한 방법 (댓글 참고)

최소 힙을 이용해서, 더 직관적으로 구할 수 있는 것 같다!
아래 댓글을 참고하여 코드를 짰다.

import heapq

n = int(input())
heights = list(map(int, input().split()))

answer = [0]*n
h = [(n-1, heights[-1])]
for i in range(n-2, -1, -1):
    height = heights[i]

    while len(h) > 0 and height >= h[0][1]:
        top_i, top_height = heapq.heappop(h)
        answer[top_i] = i+1
    heapq.heappush(h, (i, height))

for i, height in h:
    answer[i] = 0
print(*answer)