[백준] 2493 탑 - python

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

2493번: 탑

 

문제를 이해하면 다음과 같다.

높이가 다른 탑이 일렬로 있고, 모든 탑은 자기 기준 왼쪽으로 레이저를 송신한다. 수신 가능한 탑은 해당 레이저가 발사된 탑보다 높이가 크거나 같아야 하며, 레이저는 가장 먼저 닿은 탑 1개에서만 수신된다.

 

처음에 한 1시간정도 계속 뒤에서 접근해가면서 봐서 끙끙 앓았다. 앞에서 어느 탑이 수신 가능한지 알 수 없는데 뒤에서부터 본 게 잘못이었다.

 

자고 일어나서 다음날 다시 앞에서부터 보는 방향으로 생각의 방향을 틀었다. 앞에서부터 차근차근 보면 된다. 수신 가능한 탑을 배열로 저장하고, 최신순으로 꺼내보면 된다. 

 

1. 첫번째 탑 : 이전 탑이 없으므로 수신 가능한 탑 배열에 (높이, 탑번호) 넣어주기만 하면 된다.
2. 두번째 탑 : 수신 가능한 탑 배열에서 pop() 하여 높이를 비교한다. pop() 한 요소의 데이터는 prev_를 붙여 저장했고 현재 탑의 데이터는 now_를 붙여 저장했다.
   • prev_h > now_h : prev_i번째 탑이 현재 레이저를 수신 가능한 경우.
     pop()한 데이터를 다시 수신가능한 탑에 append해줘야 한다. 현재 탑 데이터도 수신 가능한 탑 배열에 append
   • prev_h == now_h : prev_i번째 탑이 현재 레이저를 수신 가능한 경우.
     높이가 같은 경우 최신 탑이 먼저 수신하게 되므로 현재 탑의 데이터만 수신 가능한 탑 배열에 append
   • prev_h < now_h : prev_i번째 탑이 현재 레이저를 수신 불가능한 경우.
     pop()한 데이터를 저장해줄 필요 없이 넘어간다.
     만약 모든 데이터를 다 훑었음에도 수신 가능한 탑이 없다면 현재 탑의 데이터를 수신 가능한 탑 배열에 append해주고 넘어간다.
3. i번쨰 탑 : 뒤와 동일한 로직이다.

이렇게 풀어주니 별 문제 없이 통과했다!

코드는 다음과 같다.

import sys

input = sys.stdin.readline

N = int(input())
Heights = list(map(int, input().split(" ")))

# 맨 앞 탑은 수신 불가능하므로 미리 저장하고 고려X
answer = [0]
available_tower = [(Heights[0], 1)]  # (높이, 탑번호)

for i in range(1, len(Heights)):
    now_h, now_i = Heights[i], i + 1

    received = False
    while len(available_tower) > 0:
        prev_h, prev_i = available_tower.pop()
        # 수신 가능한 탑 발견
        if prev_h > now_h:
            available_tower.append((prev_h, prev_i))
            answer.append(prev_i)
            available_tower.append((now_h, now_i))
            received = True
            break
        # 수신 가능한 탑 발견
        # 높이가 같은 경우 최신 탑이 더 우선이므로 최신 탑 데이터만 저장
        elif prev_h == now_h:
            answer.append(prev_i)
            available_tower.append((now_h, now_i))
            received = True
            break
        else:
            continue
    # 모든 탑이 다 수신 불가능한 경우
    if received == False:
        available_tower.append((now_h, now_i))
        answer.append(0)

print(" ".join(map(str, answer)))

 

2번 시도만에 통과했다.

 

---

현재 접근한 방법으로 문제가 안 풀릴때 빠르게 다른 방향으로 생각의 전환을 해보는 것이 중요하다고 어제 깨달았고, 오늘 직접 전환해보니 실제로 문제가 풀려서 매우 좋다. 골드 V 문제도 풀리기 시작하는 걸 보니 늘긴 느나보다.