[Python] 백준 2493번 풀이

탑

• 순서대로 주어지는 탑의 높이를 기준으로 전파가 닿는곳을 구하기 혹은 닿지 않는지를 판단하는 스텍 문제이다.

• 입력되는 탑의 높이를 스텍에 담아두고 판별한다.

• 스텍에 특정 높이의 탑이 있을 때, 다음에 들어가는 탑의 높이가 더 높다면 스텍에서 top을 지우면 된다.

  • 왜냐하면, 스텍의 top보다 높은 높이의 탑을 입력받았다면 그 이후에 입력받는 모든 탑들의 전파는 스텍 top에 있는 탑에는 절대 도달할 수 없기 때문이다.

  • 만약 스텍에 판단할 수 있는 top이 없다면 스텍에 입력을 집어넣고 0 을 출력하면 된다.

• 스텍에 특정 높이의 탑이 있을 때, 다음에 들어가는 탑의 높이가 더 낮다면 스텍에 입력받은 탑의 높이를 top으로 입력하고 이전 top의 위치를 출력해준다.

  • 왜냐하면, 이후에 입력받은 탑의 높이까지 판단해야 하기 때문에 출력과 동시에 스텍의 top으로 저장해준다.

  • 주의할점은, 이렇게 전파가 가로막혀 위치를 출력했다면 while 루프를 벗어나서 다음에 입력받는 탑의 높이로 돌아가야 한다는 것이다.

• 전파가 가로막혔을 때, 해당 탑의 위치를 출력해야 하는 문제이므로 스텍안에 “(인덱스, 탑의 높이)” 를 갖는 튜플을 저장했다.

• python 풀이

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26

import sys

n = int(sys.stdin.readline())

tower = list(map(int, sys.stdin.readline().split()))

stack = []


for idx,i in enumerate(tower):
	# print(stack)

	while stack:
		if i > stack[-1][1]:
			stack.pop()
		elif i < stack[-1][1]:
			print(stack[-1][0], end=" ")
			stack.append((idx+1,i))
			break


	if not stack:
		stack.append((idx+1,i))
		print(0, end=" ")

	else: continue

Full Code

Full Code - Python