[정올 1809] 탑

문제

일직선 위에 N개의 서로 다른 탑을 왼쪽부터 오른쪽으로 세운다.

해당 탑의 꼭대기에 있는 레이저는 왼쪽 방향으로 발사하고 발사한 신호는 가장 먼저 만나는 자신보다 큰 탑에서 수신한다. 

탑의 높이가 주어졌을 때 해당 탑에서 발사한 신호가 어떤 탑에서 수신하는지 알아보자.

 

입력

첫째 줄에 탑의 수를 나타내는 정수 N이 주어진다. N은 1 이상 500,000 이하이다.

둘째 줄에는 N개의 탑들의 높이가 직선상에 놓인 순서대로 하나의 빈칸을 사이에 두고 주어진다.

탑들의 높이는 1 이상 100,000,000 이하의 정수이다.

 

출력

첫째 줄에 주어진 탑들의 순서대로 각각의 탑들에서 발사한 레이저 신호를 수신한 탑들의 번호를 하나의 빈칸을 사이에 두고 출력한다.

만약 레이저 신호를 수신하는 탑이 존재하지 않으면 0을 출력한다.

---

접근

스택을 활용하여 이전에 어떠한 탑이 있었는지 알아본다. 

스택에 탑의 높이와 위치를 담고 현재 탑과 스택에 담긴 이전의 탑을 비교하여 계산한다.

왼쪽으로 발사했을 때 가장 먼저 만나는 탑에서 수신하기 때문에 스택을 활용하면 해당 조건을 충족할 수 있다.

 

구현

- 왼쪽에 있는 탑부터 순차적으로 탐색한다.

- 현재 스택이 비어있다면 왼쪽에 현재 탑보다 큰 높이의 탑이 없기 때문에 answer에 0을 담고,

- 스택에 현재 탑의 높이와 위치를 저장한다.

- 스택에 데이터가 존재한다면 스택의 top과 현재 탑의 높이를 비교하여 스택의 top이 크다면 수신할 수 있기 때문에

- 스택의 top에 있는 탑의 위치를 answer에 추가하고 현재 탑에 대한 정보를 스택에 저장한다.

- 만약 스택의 top보다 현재 탑의 높이가 크다면 스택을 조사하여 수신할 수 있는 탑을 찾는다.

- 조사했을 때 스택이 비었다면 answer에 0을, 존재한다면 스택의 top에 있는 탑의 위치를 answer에 저장한다.

- 그리고 스택에 현재 탑에 대한 정보를 저장한다.

for idx in range(N):
    top_height = top_list[idx]
    if len(stack) == 0:
        answer.append(0)
        stack.append((top_height, idx+1))
    else:
        if stack[-1][0] > top_height:
            answer.append(stack[-1][1])
            stack.append((top_height, idx+1))
        else:
            while stack and stack[-1][0] < top_height:
                stack.pop()
            if len(stack) == 0:
                answer.append(0)
            else:
                answer.append(stack[-1][1])
            stack.append((top_height, idx+1))

---

전체 코드

import sys
input = sys.stdin.readline

N = int(input())
top_list = list(map(int, input().split()))
stack = []
answer = []
for idx in range(N):
    top_height = top_list[idx]
    if len(stack) == 0:
        answer.append(0)
        stack.append((top_height, idx+1))
    else:
        if stack[-1][0] > top_height:
            answer.append(stack[-1][1])
            stack.append((top_height, idx+1))
        else:
            while stack and stack[-1][0] < top_height:
                stack.pop()
            if len(stack) == 0:
                answer.append(0)
            else:
                answer.append(stack[-1][1])
            stack.append((top_height, idx+1))
print(*answer)