[백준/Python] 탑

📄 문제

백준
난이도 : Gold 5
문제 제목 : 탑

✏️ 풀이 1

import sys

n = int(sys.stdin.readline())
heights = list(map(int, sys.stdin.readline().split()))
result = [0 for _ in range(n)]

for i in range(n - 1, 0, -1):
    for j in range(i - 1, 0, -1):
        if heights[i] <= heights[j]:
            result[i] = j + 1
            break

print(' '.join(map(str, result)))

가장 오른쪽 탑부터 for문을 돌면서 수신받는 탑을 찾는 풀이이다.

✏️ 풀이 2

import sys

n = int(sys.stdin.readline())
heights = list(map(int, sys.stdin.readline().split()))
stack = []
result = [0] * n

for i in range(n):
    while stack:
        if stack[-1][1] > heights[i]:
            result[i] = stack[-1][0] + 1
            break
        else:
            stack.pop()
    stack.append([i, heights[i]])

print(' '.join(map(str, result)))

다른 사람이 푼 풀이인데, '✏️ 풀이 1'과 달리 가장 왼쪽 탑부터 for문을 도는 방식이다.
우선 stack이라는 빈 스택을 선언한 뒤, 왼쪽 탑부터 [{index}, {top_height}]를 삽입하면서 의미없는(앞으로 수신받지 않을) 탑들은 제거해나가는 방법이다.

✅ stack = [] : 가장 왼쪽 탑부터 인덱스와 높이를 저장하되, 앞으로 수신받지 못할 탑(오른쪽에 있는 탑보다 작은 탑)이라는 것이 확인되면 pop() 해주어 스택에서 제거한다.

1. for문을 돌며 왼쪽 탑부터 해당 탑을 수신할 탑이 stack에 존재하는지 확인한다.
   1.1. 수신할 탑을 찾았다면, result[i]에 수신할 탑의 인덱스 + 1을 저장한다.
   1.2. 수신할 탑을 찾지 못했다면, stack.pop()을 한 뒤 while문을 한 번 더 돈다.
2. while문을 통해 stack을 모두 확인하였음에도 수신할 탑을 찾지 못한다면 수신할 탑이 존재하지 않는 것이니 result[i]는 그대로 0으로 둔다.
3. 다음 탑의 레이저를 수신할 탑을 확인하러 가기 전에(이번 loop를 끝내기 전에), 현재 발신 탑의 인덱스값과 높이를 stack에 넣어준다.

🤔 메모리, 시간 비교

정확한 메모리, 시간 비교라기 보다는 어떤 풀이가 더 효율적인지 확인해보자.

우선 '✏️ 풀이 1' 의 경우, Big-O가 $O(n)$이다. 물론 뒤에서부터 for문을 돌면서 수신할 탑을 찾으면 그 즉시 break를 걸지만, '✏️ 풀이 2'에 비해 효율적인 '수신할 탑 찾기' 방법은 아니다.

'✏️ 풀이 2' 의 경우, 정확한 Big-O를 언급하기는 어렵지만, 스택을 사용하기 때문에 각 발신 탑에 대한 수신 탑 찾기를 비교적 효율적으로 할 수 있다.
(스택에서 앞으로 수신할 탑의 대상이 되지 못할 탑, 즉 현재 발신 탑(오른쪽 탑)에 비해 키가 작은 탑은 제거하여 앞으로의 비교 대상에서 제외시켜 버리기 때문)

📦 GitHub

해당 문제, 풀이에 대한 GitHub Repository 링크는 다음과 같다.
GitHub - 백준(Gold) '2493. 탑'
GitHub - [5강] 스택/응용문제 '2493. 탑'

---