[Python] 2493. 탑(골5) / 스택

목차

1. 문제

2. 핵심 아이디어

3. 코드

4. 배운 점

---

 

1. 문제

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

2493번: 탑

---

2. 핵심 아이디어

2-1) 필요없는 건물이 무엇일까?

 

레이저는 왼쪽 방향으로 쏘아지며 

레이저를 쏜 건물보다 높은 건물에 안착한다.

 

다른 말로 높은 건물 뒤에 있는 건물들은

높이에 가려져 보이지 않기에 고려하지 않아도 되는

사실상 필요없는 건물이라고 할 수 있다.

 

예를 들어, 백준 예제 1에 있는 6 9 5 7 4 에서 

5가 레이저를 쏘는 상황이라 했을 때

 

6  9  <-5

 

사실상 6은 9에 가려져 보이지 않는다.

즉 고려해줄 필요가 없다.

 

마찬가지로 4가 레이저를 쏠 때

6  9  5  7   <- 4 

 

5는 7에 가려져 보이지 않는다.

즉 고려할 필요가 없다.

 

2-2) 고려하는 건물만 남기는 방법?

 

이제 필요없는 건물이 무엇인지 알았다.

그럼 고려해야할 건물들만 남기는 방법은 무엇일까?

 

결론부터 말하면

내 건물보다 높이가 낮은 건물들을 모두 철거하다가

내 건물보다 높은 건물을 만나면 철거를 중지하면 된다.

 

스택 자료구조를 활용할 것이기에 용어를 수정하면

내 건물보다 높이가 낮은 건물들을 모두 pop하다가

내 건물보다 높은 건물을 만나면 pop을 중지하면 된다.

 

그럼 이게 대체 무슨 의미인지 예제를 통해 살펴보자

answer=[] //정답이 담길 리스트

top= []      // 고려해주어야 할 건물들

---

6 9 5 7 4

 

먼저 6이다.

6이 쏜 레이저를 받을 건물이 없다. (len(top)==0)

 

answer에는 0을 넣어주고

그럼 top에 첫번째 건물의 높이를 라벨링하여 넣어준다.

 

top=[(6,1)] ==> (높이, 번지수)

answer=[0]

---

6 9 5 7 4

다음으로 9이다.

 

9를 기준으로 레이저를 받을 건물이 있는지 확인하자

top=[(6,1)] <== (9,2)

answer=[0]

 

건물 높이 6이 있다.

이 건물은 어짜피 높이9인 나의 건물에 가려질 운명이다.

필요없는 건물이 되므로 pop해준다.

 

top=[]

answer=[]

 

이젠 레이저를 받을 탑이 없다. 앞과 같이 top과 answer에 값을 추가해준다.

top=[(9,2)]  ==> (높이, 번지수)

answer=[0,0]

---

6 9 5 7 4

다음으로 5이다.

 

top을 살펴보자

top=[(9,2)]  <== (5,3)

answer=[0,0]

 

이번엔 5보다 큰 9를 만났다. 

즉, 나의 레이저를 받아줄 건물을 만났다.

 

그럼 answer에 그 건물읠 번지수(2)를 추가하고

top에 내 건물을 넣어주자.

 

top=[(9,2) ,  (5,3) ]

answer=[0,0,2]

---

6 9 5 7 4

다음으로 7의 차례이다.

 

top을 살펴보자

top=[(9,2) ,  (5,3) ]

answer=[0,0,2]

 

첫 탑인 5는 내 레이저를 받지 못한다. 5<7

5는 어차피 높이 7인 지금 건물로 인해 가려질 운명이다. 철거해주자

top=[(9,2) ] => pop (5,3))

answer=[0,0,2]

 

이번엔 9를 만났다.

9는 내 레이저를 받아줄 수 있다.

 

answer에 9의 번지수를 담고

내 건물을 담아준다.

top= [(9,2) , (7,4)]

answer=[0,0,2,2]

 

---

6 9 5 7 4

마지막 4이다.

 

top을 살펴보자

top= [(9,2) , (7,4)] <= (4,5)

answer=[0,0,2,2]

 

첫 탑인 7은 내 레이저를 받아줄 수 있다.

answer의 높이 7건물의 번지수를 추가하고

top에 내 건물을 추가한다.

 

top= [(9,2) , (7,4) , (4,5)]

answer=[0,0,2,2 ,4]

 

이제 answer 값을 구했다.

 

이 과정을 코드로 구현하면...........

 

---

3. 코드

#탑
#고려해야할 건물들만 내림차순으로 정렬되게 만듦

from collections import deque
import sys

input= lambda: sys.stdin.readline().strip('\n')
n= int(input())

tmp= list(map(int, input().split()))
top=[]
answer=[]

for idx, i in enumerate(tmp):
  #고려할 탑이 있고, 내 건물에 가려질 운명이라면 == 내 건물보다 작다면
  while(top and top[-1][0]<i): 
    top.pop()
  
  #고려할 탑이 없을 때
  if len(top)==0:
    answer.append(0)
    top.append([i,idx+1])
-    continue
  
  #내 레이저를 받아줄 건물의 번지수 추가
  answer.append(top[-1][1])
  
  #내 건물 추가
  top.append([i, idx+1])


print(*answer)

---

4.배운점

스택 구조에서 배우는 중위 -> 후위 연산자 와 비슷하지 않았나 싶다.

스택 구조 자체에 대한 이해도 중요하지만 이를 문제해결과 연관시키는 능력도 중요하다는 것을 느꼈다.