[백준] (2493) 탑 [Python]

🔗 문제 링크

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

문제

• KOI 통신연구소는 레이저를 이용한 새로운 비밀 통신 시스템 개발을 위한 실험을 하고 있다. 실험을 위하여 일직선 위에 N개의 높이가 서로 다른 탑을 수평 직선의 왼쪽부터 오른쪽 방향으로 차례로 세우고, 각 탑의 꼭대기에 레이저 송신기를 설치하였다. 모든 탑의 레이저 송신기는 레이저 신호를 지표면과 평행하게 수평 직선의 왼쪽 방향으로 발사하고, 탑의 기둥 모두에는 레이저 신호를 수신하는 장치가 설치되어 있다. 하나의 탑에서 발사된 레이저 신호는 가장 먼저 만나는 단 하나의 탑에서만 수신이 가능하다.
• 예를 들어 높이가 6, 9, 5, 7, 4인 다섯 개의 탑이 수평 직선에 일렬로 서 있고, 모든 탑에서는 주어진 탑 순서의 반대 방향(왼쪽 방향)으로 동시에 레이저 신호를 발사한다고 하자. 그러면, 높이가 4인 다섯 번째 탑에서 발사한 레이저 신호는 높이가 7인 네 번째 탑이 수신을 하고, 높이가 7인 네 번째 탑의 신호는 높이가 9인 두 번째 탑이, 높이가 5인 세 번째 탑의 신호도 높이가 9인 두 번째 탑이 수신을 한다. 높이가 9인 두 번째 탑과 높이가 6인 첫 번째 탑이 보낸 레이저 신호는 어떤 탑에서도 수신을 하지 못한다.
• 탑들의 개수 N과 탑들의 높이가 주어질 때, 각각의 탑에서 발사한 레이저 신호를 어느 탑에서 수신하는지를 알아내는 프로그램을 작성하라.

입력

첫째 줄에 탑의 수를 나타내는 정수 N이 주어진다. N은 1 이상 500,000 이하이다. 둘째 줄에는 N개의 탑들의 높이가 직선상에 놓인 순서대로 하나의 빈칸을 사이에 두고 주어진다. 탑들의 높이는 1 이상 100,000,000 이하의 정수이다.

출력

첫째 줄에 주어진 탑들의 순서대로 각각의 탑들에서 발사한 레이저 신호를 수신한 탑들의 번호를 하나의 빈칸을 사이에 두고 출력한다. 만약 레이저 신호를 수신하는 탑이 존재하지 않으면 0을 출력한다.

💻 코드 제출

1st Try:

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

n = int(input())
a = deque(map(int, input().split()))
b = deque()

def tower(i):
    if not a or i > max(a):
        return 0
    for j in range(len(a)-1, -1, -1):
        if a[j] >= i:
            return j+1
    return 0

cnt = 0
while cnt < n:
    k = a.pop()
    b.appendleft(tower(k))
    cnt += 1

print(*b)

시간 초과가 발생하여 정답을 받는 데 실패하였다.

2nd Try:

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

n = int(input())
t = deque(map(int, input().split()))
stack = deque()
answer = [0] * n

for i in range(n):
    while stack and t[stack[-1]] < t[i]:
        stack.pop()

    if stack:
        answer[i] = stack[-1] + 1
            
    stack.append(i)

print(*answer)

시간을 단축시키기 위해 answer(b) 배열을 deque에서 리스트로 변환하고 코드의 전체적인 동작 과정을 수정했다. 하지만 여전히 시간 초과가 발생하였다.

3rd Try:

import sys
input = sys.stdin.readline

n = int(input())
t = list(map(int, input().split()))
stack = list()
answer = [0] * n

for i in range(n):
    while stack and t[stack[-1]] < t[i]:
        stack.pop()

    if stack:
        answer[i] = stack[-1] + 1
            
    stack.append(i)

print(*answer)

deque()로 선언했던 스택들을 list()로 선언하였더니 시간 초과 문제를 해결할 수 있었다.

🔎 코드 분석

일반적으로 deque()가 list()보다 빠른 시간 복잡도를 제공하기 때문에 스택과 큐를 구현하는 데에 있어 list()보다 더 좋다고 알고 있다. 하지만 이번 문제에서는 오히려 list()를 사용했을 때의 시간 복잡도가 더 빨랐다.

 

deque와 list는 각각의 특성과 사용처가 다르기 때문에, 특정 상황에서는 list가 더 빠르게 동작할 수 있다.

• 메모리 관리: deque는 양쪽 끝에서의 삽입과 삭제를 지원하기 위해 더 많은 메모리를 할당하고 관리한다. 반면 list는 단순히 배열처럼 연속된 메모리 공간을 사용하므로 메모리 관리가 더 효율적일 수 있다.
• 연산의 오버헤드: deque는 양쪽 끝에서의 삽입과 삭제를 최적화하기 위해 추가적인 오버헤드가 있다. 반면, 스택처럼 한쪽 끝에서만 삽입과 삭제를 수행하는 경우에는 list가 더 간단하게 동작한다.
• Python의 구현 세부사항: Python의 list는 내부적으로 동적 배열로 구현되어 있어, 요소를 추가하거나 제거할 때 최적화된 성능을 제공한다. 특히, 스택의 경우 append()와 pop() 연산이 평균적으로 O(1)로 작동한다.
• 사용 패턴: 이번 경우 코드에서 스택의 마지막 원소에 대한 접근 및 추가/삭제만 수행하고 있기 때문에, list가 이러한 패턴에 더 적합하다. deque는 주로 양쪽 끝에서의 빈번한 삽입과 삭제가 필요한 경우에 더 유리하다고 한다.

결론적으로, 이번 문제의 경우에는 스택의 한 쪽 끝에서만 작업을 수행하였기 때문에 list를 사용하는 것이 더 효율적이었다.