[백준] 2493번. 탑 🗼

[백준] 2493번. 탑 🗼

아이디어

• 처음엔 그냥 내 다음번에 나오는 나보다 큰 탑이 나올때까지 반복문을 돌렸는데 시간초과 났다..
• stack을 이용해서 푸는 전형적인 문제였다..... 아직 내 수준에서 생각해내진 못할 것 같다.... 🤯

1. 레이저를 쏘는 방향 반대로(왼 → 오) 탐색하면서 보조 stack에 넣는다.
2. 현재 레이저를 쏘는 탑과 stack의 마지막(top) 값을 비교하여 레이저를 수신할 수 있는지 체크한다.
   2-1. 수신할 수 있다면(왼쪽 탑(stack[-1])이 더 크다면), 그 탑의 인덱스를 result 리스트에 넣어주고
   2-2. 수신할 수 없다면(더 작은 탑이라면), 더 이상 사용되지 않으므로 pop()해준다.
3. stack에 그 검사를 마친 탑을 넣어준다.
4. 1-3을 반복한다.

stack	왼쪽 탑	쏠 수 있는지 여부(>)	현재 탑	탑 리스트	result
[]	-	False	6	[9, 5, 7, 4]	[0]
[6]	6	False	9	[5, 7, 4]	[0, 0]
[9]	9	True	5	[7, 4]	[0, 0, 2]
[9, 5]	5	False	7	[4]	[0, 0, 2]
[9]	9	True	7	[4]	[0, 0, 2, 2]
[9, 7]	7	True	4	[]	[0, 0, 2, 2, 4]

• stack을 리스트로 사용하지말고 deque을 사용하면 시간복잡도를 줄일 수 있다. 💡pop()을 쓸 땐 최대한 deque을 쓰자!!
  • list.pop() : O(N)
  • deque.pop() : O(1)

시간 복잡도

• O(N)

코드

• deque 이용(O(N))

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

n = int(input())
towers = [(i + 1, t) for i, t in enumerate(map(int, input().split()))]
stack = deque([towers[0]])
result = [0]

for j in range(1, n):
    tower = towers[j][1]
    razer = 0

    # 비교할 대상이 있으면
    while stack: 
        # 왼쪽에 있는 탑이 나보다 작으면 쓸모없어지니까 없앤다
        if tower > stack[-1][1]:
            stack.pop() 
        
        # 나보다 크면 레이저 수신 가능
        else:
            razer = stack[-1][0]
            break
        
    stack.append((j + 1, tower))
    result.append(razer)

print(*result)

• stack 이용 (O(N^2))

import sys
input = sys.stdin.readline

n = int(input())
towers = [(i + 1, t) for i, t in enumerate(map(int, input().split()))]
stack = [towers[0]]
result = [0]

for j in range(1, n):
    tower = towers[j][1]
    razer = 0

    # 비교할 대상이 있으면
    while stack: 
        # 왼쪽에 있는 탑이 나보다 작으면 쓸모없어지니까 없앤다
        if tower > stack[-1][1]:
            stack.pop() 
        
        # 나보다 크면 레이저 수신 가능
        else:
            razer = stack[-1][0]
            break
        
    stack.append((j + 1, tower))
    result.append(razer)

print(*result)

• 시간초과 코드 (O(N^2))

import sys
input = sys.stdin.readline

n = int(input())
stack = list(map(int, input().split()))
stack.reverse()
result = []

for i, tower in enumerate(stack):
    answer = 0
    for j in range(i + 1, n):
        if tower <= stack[j]:
            answer = n - j
            break
    result.append(answer)

result.reverse()
print(*result)