2493번 - 탑(python3)

문제 링크 : https://www.acmicpc.net/problem/2493

2493번: 탑

처음에는 리스트를 훑으면서 접근하려고 했다가 스택을 사용해서 간단하게 해결할 수 있었던 문제입니다. 모든 탑이 레이저를 왼쪽 방향으로 발사하니까 주어진 탑의 가장 끝부터 훑으면 됩니다. 틀렸다는 메세지가 나오는데, start를 이용해서 수신할 수 있는 탑이 어디까지인지를 나타내고자 했는데, 여기서 문제가 발생한 것 같습니다.

#틀린 코드

n = int(input())
lst = list(map(int, input().split()))

sol = [0]*n
max_h = lst[-1] #마지막 탑만 탐색했을 때 가장 높은 탑은 마지막 탑
start = n

for idx in range(n-2, -1, -1): #뒤쪽부터
    if lst[idx] >= max_h: #새로 발견한 탑이 기존 최고 탑과 같은 높이이거나 더 높으면
        max_h = lst[idx]  #업데이트
        sol[idx+1:start] = [idx+1]*(start-(idx+1)) #새로 발견한 탑 이전까지 업데이트
        start = idx+1

for i in range(n):
    print(sol[i], end = ' ')

다음은 스택을 이용해서 더 간단하게 해결한, 맞는 코드입니다.

stack = []
sol = [0]*n

for idx in range(n-1, -1, -1):
    while stack and lst[stack[-1]] < lst[idx]:
        sol[stack.pop()] = idx+1
    stack.append(idx)
print(*sol)

원래 코드에서는 start를 이용해서 레이저를 수신할 수 있는 탑 A가 나오면 탑 A가 어느 탑까지 수신할 수 있는지를 체크하려고 했는데, 그 역할을 스택을 이용하면 더 간단하게 할 수 있습니다. 스택이 비어있다면 현재 수신하지 못하는 경우가 없다는 의미이고, 스택이 비어있지 않으면서 수신할 수 있는 탑 A가 나타난다면 A가 수신할 수 있는 가능한 모든 탑을 스택에서 꺼냅니다.

 

여담으로 print(*lst) 이렇게 출력하는 걸 처음 배웠네요. 유용하게 써먹을 수 있겠습니다.