[정올 1328] 빌딩

문제

N개의 빌딩이 있으며 빌딩은 1번부터 N번까지의 번호가 있다.

빌딩이 X 좌표 상에 위치해 있으며 i 좌표에 있는 빌딩은 Hi 만큼의 높이를 갖고있다.

만약 i < j 일 때 Hi < Hj면 i번 빌딩에서 j번 빌딩을 볼 수 있는 것이다.

각 좌표에 빌딩의 높이가 주어졌을 때 가장 가까이 보이는 빌딩을 찾아보자.

 

입력

첫 번째 줄에 N이 입력되며

이어서 N개의 줄에 빌딩의 높이가 입력된다.

 

출력

총 N개의 줄에 빌딩의 위치를 출력한다.

---

접근

N이 100,000 이하로 입력되기 때문에 이중 for문 이상으로는 해결할 수 없다. 따라서 한 개의 for문으로 어떻게 풀어야하는지 생각한다.

이번 문제에서 끝에 있는 빌딩부터 탐색을 진행한다. 끝에 있는 빌딩을 스택에 넣고 탐색을 진행하면서 스택의 top이 현재 빌딩보다 높다면 스택의 top에 있는 빌딩을 볼 수 있는 것이다. 만약 스택의 top에 있는 빌딩의 높이가 더 작다면 교체를 한다. 스택의 top에는 계속해서 최고높이를 담게된다.

 

구현

- 빌딩의 정보가 입력된 H를 반대에서부터 탐색을 진행한다.

- 현재 스택의 top이 h보다 크다면 해당 빌딩을 볼 수 있기 때문에 answer에 스택의 top에 대한 위치를 추가한다.

- 그리고 스택에는 현재 탑에 대한 정보를 추가한다.

- 만약 스택의 top이 h보다 작다면 큰 것이 나올 때까지 스택을 pop한다.

- 그리고 스택의 top을 answer에 추가하고 없다면 0을 추가한다.

- 이어서 스택에 현재 탑에 대한 정보를 추가한다.

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

- answer를 뒤집어서 새롭게 저장하며 이를 한 줄에 하나씩 출력한다.

answer = list(reversed(answer))
for ans in answer:
    print(ans)

---

전체 코드

import sys
input = sys.stdin.readline

N = int(input())
H = []
for _ in range(N):
    H.append(int(input()))

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

answer = list(reversed(answer))
for ans in answer:
    print(ans)