[BOJ] 2493번: 탑

문제

 

입출력 예시

문제를 요약하면 '내 왼쪽 인근에 있으면서 나보다 높은 탑의 인덱스 출력'이라고 할 수 있겠다. '인근'이라는 표현을 쓴 이유는 높이가 4인 다섯번째 탑처럼 왼쪽에 있는 탑들 중 나보다 높은 탑이 여러 개인 경우가 있을 수 있기 때문이다. 7보다 더 높은 탑이 있지만 4가 쏜 레이저 신호는 이미 7에 닿았으므로 7의 인덱스 번호+1을 출력하면 된다.

 

풀이

☝ 첫 번째 시도(시간 초과)

import sys
from collections import deque

N = int(input())

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

received = [0]

for i in range(1, N):
    candidate = deque(tower[:i])
 
    flag = 0
    
    if max(candidate) <= tower[i]:
        received.append(0)
    else:
        while flag == 0:
            if candidate[-1] < tower[i]:
                candidate.pop()
            else:
                flag = tower.index(candidate.pop())+1                
                received.append(flag+1)
            
print(*received)

 

코드 흐름 간단 설명용 접은글

1. 탑 개수만큼 for문을 돌리는데 각 for문 안에서 슬라이싱을 이용해 i번째 탑과 비교할 탑 목록(candidate) 생성

2. candidate의 max 값이 현재 탑 높이보다 작을 경우 레이저를 수신할 탑이 없다는 뜻이기 때문에 정답 저장용 배열에 0 append

3-1. 현재 탑의 레이저 신호를 받을 탑 확인용 flag가 0일 때만 while문 반복

3-2. candidate의 마지막 탑 높이가 현재 탑 높이보다 낮을 경우 candidate에서 빼버리고 뒤에서부터 탑 높이 체크

 

이 흐름에서 크게 변하지 않고 몇 번 더 시도해봤는데도 계속 시간 초과가 떴다. 'for문이 하나 밖에 없는데 어디서 시간 초과가 걸리지?' 이 생각을 계속 해보다가 스스로 답을 찾지 못해 백준 질문 검색란과 구글의 도움을 받았다.

 

정말 생각지도 못했는데 시간 초과의 원인은 슬라이싱이었다. N개의 요소에 대해 매번 슬라이싱을 하기 때문에 보이는 것과 달리 실질적인 시간복잡도는 O(N^2)이 된다고 한다. 혼자서는 절대 못 알아챘을 듯

 

 

🖖 네 번째 시도(스택 활용, 성공)

import sys
from collections import deque

N = int(sys.stdin.readline().rstrip())

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

stack = []
received = [0 for _ in range(N)]

for i in range(N):
    while stack:
        if stack[-1][1] <= tower[i]:
            stack.pop()
        else:
            received[i] = stack[-1][0]
            break
         
    stack.append([i+1, tower[i]])

print(*received)

 

파이썬에서 사용하는 스택은 append(), pop()만 쓸 줄 알면 된다고 생각했지 제대로 활용하지 못했다. 탑 인덱스와 높이를 한꺼번에 저장해놓고 스택의 마지막 요소를 꺼내면서 현재 높이와 비교해주면 슬라이싱을 쓸 때처럼 매번 새로운 요소를 생성할 필요가 없다. 항상 생각을 하고 문제를 풀자 😖