[Python 파이썬] 백준 2493번 - 탑

2023년 11월 21일

문제 링크 : 백준 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을 출력한다.

알고리즘 분류

• 자료구조
• 스택

---

문제 접근

문제가 말하는 바는 다음과 같다.

 

 

서로 다른 높이의 탑이 위와 같이 일직선 상에 있을 때, 각 탑이 왼쪽으로 레이저를 발사했을 때 가장 먼저 받는 타워는 각각 몇 번째 타워인지 구하는 문제이다. ( 레이저 통신은 타워를 통과하지 않으며, 한 타워가 수신하면 레이저 통신은 사라지는 매커니즘이다. )

 

 

 

 

위 두 타워와 같이 왼쪽에 타워가 더 없거나 자신보다 큰 타워가 없어 송신한 레이저를 수신받는 타워가 없는 경우, 0을 기입하며

 

 

 

 

 

위의 경우처럼 왼쪽으로 레이저를 송신했을 때 자신보다 더 높은 타워가 존재해 레이저를 수신받는 타워는 몇 번째 타워인지 기입하면 된다.

 

문제의 데이터 수인 타워 수가 500,000이기에 무식하게 앞에서부터 하나씩 모두 비교해보면 시간초과가 날 것이라 예상되어 스택 구조를 활용해 접근해보기로 하였다.

 

여기서 첫 번째 타워부터 스택에 담으며 비교해보는 것이 아닌, 가장 마지막 타워부터 순서대로 스택에 담으며 비교해보기로 결정했다.

왜냐하면, 레이저는 오른쪽에서 왼쪽으로 발사되며 가장 먼저 수신받는 타워의 인덱스 번호를 구하는 것이기 때문에 왼쪽부터 비교하면 가장 먼저 수신받는 타워를 알아내기에 어렵다고 판단되었기 때문이다.

 

---

순서도

 

1. 입력값을 입력받고, 타워 높이 데이터를 tower 리스트에 담는다

2. 만약 레이저를 수신받는 타워가 특정되면, 해당 타워가 몇 번째 타워인지 빠르게 알아야 한다. 
	
이에 키 : 값 쌍을 타워 높이 : 타워 인덱스 번호 쌍으로 저장할 tower_dict 딕셔너리를 선언 및 각 키:값 쌍을 삽입한다.

3. stack을 선언하고, 결과를 담을 result를 선언한다. result는 타워 개수 길이의 리스트로 선언하며 초기 값은 0

4. tower 리스트의 마지막부터 비교하며, tower 리스트의 첫 번째 타워를 비교할 때까지 반복문 수행

4-1. 현재 비교하는 타워의 높이를 new_tower에 담음
    
4-2. new_tower가 stack[-1] 보다 크면, stack[-1] 높이에 해당되는 타워가 쏜 레이저는 new_tower가 수신받는다는 의미.
    	
result에 stack[-1]가 쏜 레이저는 new_tower가 수신받는 것을 기록해주고, stack[-1]을 pop해준다.
    
4-3. 4-2 과정이 성립되지 않거나 stack이 빌 때까지 반복 후, new_tower를 stack에 append하고 그 다음 타워를 비교한다.

5. 4 과정이 모두 끝나 반복문이 종료되면 result를 출력한다.

 

---

입력 예제

 

5
6 9 5 7 4

 

위 순서도대로 예제를 풀어보겠다.

 

초기 상태

 

초기 상태이며 우리는 마지막 타워부터 시작해 첫 번째 타워까지 역순으로 비교할 것이다.

 

현재 마지막 타워의 높이인 4를 new_tower에 저장한다.

 

 

 

stack의 마지막 요소와 비교하려 했으나 stack이 비어있기 때문에 new_tower를 stack에 append해준다.

 

 

 

 

다음으로 비교할 타워의 높이 7을 new_tower에 저장한다.

그리고 stack의 마지막 요소인 4와 비교해 보았을 때, new_tower가 더 높기 때문에 높이가 4인 타워가 쏜 레이저는 높이가 7인 타워가 수신받게 된다.

높이가 4인 타워의 레이저는 어떤 타워가 수신받는지 특정되었으니 stack.pop() 해준다.

 

 

높이가 4인 타워의 레이저 통신은 높이가 7인 타워가 수신받게 되니, result에 해당 정보를 기록한다.

더 비교를 하려 했으나, stack이 비어있으므로 new_tower를 stack에 append해준다.

 

 

다음 순서인 높이가 5인 타워를 비교해보자. 높이 5를 new_tower에 저장하고, stack의 마지막 요소와 비교해보니, new_tower가 더 작다. 이는 높이가 7인 타워가 쏜 레이저는 new_tower가 수신받지 못한다는 의미이다.

더 비교할 수 없으니 new_tower를 stack에 append해준다.

 

 

다음 순서인 높이가 9인 타워를 비교해보자. 높이 9를 new_tower에 저장하고, stack의 마지막 요소와 비교해보니, new_tower가 더 큰 것을 확인할 수 있다. 이는 높이가 5인 타워가 쏜 레이저를 높이가 9인 타워가 수신받게 된다는 의미이다. 

높이가 5인 타워의 레이저는 어떤 타워가 수신받는지 특정되었으니 stack.pop() 해주고, result에 기록해준다.

 

pop 후, stack의 마지막 요소를 비교해보자.

 

 

 

new_tower과 stack의 마지막 요소를 비교해보니 new_tower가 더 큰 것을 확인할 수 있다. 이는 높이가 7인 타워가 쏜 레이저를 높이가 9인 타워가 수신받게 된다는 의미이다.

높이가 7인 타워의 레이저는 어떤 타워가 수신받는지 특정되었으니 stack.pop() 해주고, result에 기록해준다.

 

 

더 비교를 해보려 했지만, 스택이 비어있기 때문에 new_tower를 stack에 append 해준다.

 

 

 

 

다음 순서의 타워의 높이를 new_tower에 대입해준다.

이후 스택의 마지막 요소인 9와 비교해보니 new_tower가 더 작기에 new_tower를 stack에 append 해준다.

 

 

 

tower 리스트의 모든 요소를 순회하였기에 로직 수행을 종료하고 result를 출력하면 원하는 답이 된다.

 

출력 예제

 

0 0 2 2 4

 

 

---

주의할 점

 

tower 리스트의 역순으로 탐색해야 하는 점을 이해하지 못한다면 문제 접근이 까다로울 것이라 생각된다.

 

---

전체 코드

# 2493

def solution(N):
    stack = []
    result = [0] * N

    N -= 1
    stack.append(tower[N])
    N -= 1
    
    while N >= 0:
        new_tower = tower[N]
        while True:
            if stack and stack[-1] < new_tower:
                result[tower_dict[stack[-1]]] = tower_dict[new_tower] + 1
                stack.pop()
            else:
                break
        stack.append(new_tower)
        
        N -= 1
 
    for x in result:
        print(x ,end = " ")
        
        

if __name__ == "__main__":
    N = int(input())

    tower = list(map(int, input().split()))
    
    tower_dict = {}
    for i in range(N):
        tower_dict[tower[i]] = i

    solution(N)

 

---

풀이 후기

 

문제 접근 단계에서 시간복잡도를 예상하고 빠르게 스택 자료구조를 활용할 방안을 고려할 수 있었기 때문에 빠른 문제 풀이가 가능했다.