백준 - 탑(2493) Python

www.acmicpc.net/problem/2493

2493번: 탑

탑들이 일렬로 서있다. 각 탑의 꼭대기에서 왼쪽을 보았을 때, 높이가 같거나 높은 가장 가까운 탑을 출력하는 문제이다. 만약 없다면, 0을 출력한다.

 

* 힌트

1. 스택을 활용한다.

2. i번째 탑의 높이보다 i+1번째 탑의 높이가 높다면, i번째 탑은 i+1번 이후 탑들의 신호를 수신하지 못한다.

 

* 풀이

스택을 생성하고, 신호를 수신할 가능성이 있는 탑들은 스택에 추가한다. 

 

  1. 앞에서부터 순차적으로 탐색한다. 0<=i<len(tower_list)

  2. 스택이 비었을 때는 수신 가능한 탑이 없다는 뜻이므로 0을 출력하고 스택에 i번째 탑의 [높이, index]를 추가한다. 

  3. 스택이 비지 않았다면, 스택에 들어있는 탑들에 대하여 높이가 현재 탑의 높이보다 같거나 높은지 비교한다.(현재 탑의 신호를 수신할 수 있는지 확인)

  4. 현재 탑보다 높이가 낮은 것은 스택에서 pop하고, 높은 것이 있다면 해당 탑의 Index를 출력하고 스택의 현재 탑을 추가한다. 스택 탐색을 멈춘다.

  5. 1~4번을 tower_list의 끝까지 반복한다.

 

* 예제  

 

탑들이 위 그림과 같이 주어져 있다.

각 탑들의 신호를 몇번째 탑에서 수신하는지 확인해본다.

 

첫번째 탑의 신호 : 받을 수 있는 탑이 없다. → 0을 출력

두번째 탑의 신호 : 받을 수 있는 탑이 없다. → 0을 출력

세번째 탑의 신호 : 두번째 탑이 수신한다.  → 2을 출력

네번째 탑의 신호 : 두번째 탑이 수신한다. → 2을 출력

다섯번째 탑의 신호 : 네번째 탑이 수신한다 → 4을 출력

 

정답 : 0 0 2 2 4

 

그럼 위의 예제를 실제 코드로 테스트해본다.

* Index에 주의 : 첫번째 탑의 Index  0* 

 

tower_list = [6, 9, 5, 7, 4]

 

[1] 첫번째 탑 : index = 0, 탑의 높이 = 6, 스택 = []

 

  1) 스택이 비어 있으므로, 스택에 [6(탑의 높이), 0(탑의 Index)]를 추가한다.

  2) 스택이 비어있다는 뜻은, index 0번 탑의 신호를 수신할 수 있는 탑이 없다는 것을 의미하므로 0을 출력한다.

 

output = '0'

 

[2] 두번째 탑 : index = 1, 탑의 높이 = 9 스택 = [ [6,0] ]

 

  1) 스택이 비지 않았으므로, 비교를 시작한다. 

  2) 스택의 첫번째 원소 : [6,0]

      현재 탑의 높이 : 9 > 6 이므로 첫번째 원소를 pop한다.

  3) 스택이 비었으므로 두번째 탑의 신호를 수신할 수 있는 탑은 없다.

     현재 탑의 높이와 인덱스를 스택에 추가한다.

 

output = '0 0'

 

[3] 세번째 탑 : index = 2, 탑의 높이 = 5 스택 = [ [9,1] ]

  

  1) 스택이 비지 않았으므로, 비교를 시작한다.

  2) 스택의 첫번째 원소 : [9,1]

      현재 탑의 높이 : 5 < 9 이므로 해당 탑에서 세번째 탑의 신호를 수신한다.

      높이 9인 탑의 index +1(2)를 출력하고, 현재 탑의 높이와 인덱스 [5,2]를 스택에 추가한다.

 

output = '0 0 2'

 

[4] 네번째 탑 : index = 3, 탑의 높이 = 7, 스택 = [ [9,1], [5,2] ]

 

  1) 스택이 비지 않았으므로, 비교를 시작한다. (스택의 오른쪽부터 탐색한다. 이는 가장 가까운 탑부터 탐색한다는 의미이다.)

  2) 스택의 첫번째 원소 : [5,2]

      현재 탑의 높이 : 7 > 5이므로, 해당 탑을 pop하고 다음 탑과 비교한다.

  3) 스택의 두번째 원소 : [9,1]

      현재 탑의 높이 : 7 < 9이므로, 해당 탑에서 네번째 탑의 신호를 수신한다.

      높이가 9인 탑의 index + 1(2)을 출력하고, 현재 탑의 높이와 인덱스 [7,3]을 스택에 추가한다.

 

output = '0 0 2 2'

 

[4] 다섯번째 탑 : index = 4, 탑의 높이 = 4, 스택 = [ [9,1], [7,3] ]

 

  1) 스택이 비지 않았으므로, 비교를 시작한다.

  2) 스택의 첫번째 원소 : [7,3]

      현재 탑의 높이 : 4 < 7이므로, 해당 탑에서 다섯번째 탑의 신호를 수신한다.

      높이가 7인 탑의 index + 1(4)를 출력하고 현재 탑의 높이와 인덱스 [4,4]를 스택에 추가한다.

 

최종 output = '0 0 2 2 4'

스택 : [ [9,1], [7,3], [4,4] ]

 

import sys
r = sys.stdin.readline

# 입력 받기
n = int(r())
t_list = list(map(int, r().split()))
answer = []
stk = []
for i in range(n):
    h = t_list[i]
    if stk:
        #print(stk)
        while stk:
            if stk[-1][0] < h :
                stk.pop()
                if not stk:
                    print(0, end=' ')
            elif stk[-1][0] > h:
                print(stk[-1][1]+1, end=' ')
                break
            else : 
                print(stk[-1][1]+1, end=' ')
                stk.pop()
                break
        stk.append([h, i])
    else:
        print(0, end=' ')
        stk.append([h,i])