[Python/파이썬] 백준 22866번 탑 보기

22866번: 탑 보기

 

문제

일직선으로 다양한 높이의 건물이 총 $N$개가 존재한다. 각 건물 옥상에서 양 옆에 존재하는 건물의 옆을 몇 개 볼 수 있는지 궁금해졌다.

 $i$번째 건물 기준으로 $i - 1$, $i - 2$, ..., $1$번째 건물은 왼쪽에, $i + 1$, $i + 2$, ..., $N$번째 건물은 오른쪽에 있다. 각 건물 사이의 거리는 다 동일하다.

현재 있는 건물의 높이가 $L$이라고 가정하면 높이가 $L$보다 큰 곳의 건물만 볼 수 있다.

바라보는 방향으로 높이가 $L$인 건물 뒤에 높이가 $L$이하인 건물이 있다면 가려져서 보이지 않는다.

번호	1	2	3	4	5	6	7	8
높이	3	7	1	6	3	5	1	7
보이는 건물 번호	2	x	2, 4, 8	2, 8	2,4,6,8	2,4,8	2,4,6,8	x

각 건물에서 볼 수 있는 건물들이 어떤것이 있는지 구해보자.

입력

첫번째 줄에 건물의 개수 $N$이 주어진다.

두번째 줄에는 $N$개의 건물 높이가 공백으로 구분되어 주어진다.

출력

$i(1 \le i \le N)$번째 건물에서 볼 수 있는 건물의 개수를 출력한다.

만약 볼 수 있는 건물의 개수가 1개 이상이라면 $i$번째 건물에서 거리가 가장 가까운 건물의 번호 중 작은 번호로 출력한다.

코드

import sys
input = sys.stdin.readline

n = int(input())
l = [0] + list(map(int, input().split()))

ans = [[0, -int(1e9)] for _ in range(n+1)]

# 건물보다 왼쪽
stack = []
for i in range(1, n+1):
    while stack and l[stack[-1]] <= l[i]:   # 나보다 작은 건물 pop
        stack.pop()
    # 왼쪽에 보이는 건물 ans에 추가
    ans[i][0] += len(stack)     # 왼쪽으로 볼 수 있는 건물 개수
    if stack:
        ans[i][1] = stack[-1]   # 보이는 건물 중 가장 가까운 건물
    stack.append(i)

# 건물보다 오른쪽
stack = []
for i in range(n, 0, -1):
    while stack and l[stack[-1]] <= l[i]:   # 나보다 작은 건물 pop
        stack.pop()
    # 오른쪽에 보이는 건물 ans에 추가
    ans[i][0] += len(stack)     # 오른쪽으로 볼 수 있는 건물 개수
    if stack and stack[-1]-i < i-ans[i][1]:
        ans[i][1] = stack[-1]   # 보이는 건물 중 가장 가까운 건물
    stack.append(i)

for i in range(1, n+1):
    if ans[i][0] != 0:
        print(ans[i][0], ans[i][1])
    else:
        print(0)

현재 있는 건물에서 양쪽으로 어떤 건물들이 보이는지 알아야 한다.

이를 알아보기 위해 자료구조 중 스택을 이용한다. 그리고 한번에 양쪽을 보긴 어렵기 때문에 왼쪽에서부터 한 번, 오른쪽에서부터 한 번 탐색한다.

 

탐색하는 과정은 다음과 같다.

1. 스택에 있는 건물 중 나보다 작은 건물들은 pop해버린다.
   (현재 건물(i)보다 작은 건물은 어차피 현재 건물에 가려서 안 보이게 될 것이기 때문에)
2. stack에 남은 건물들은 나보다 큰 건물들로 현재 건물에서 보이는 건물들이다. 이 값을 ans[i][0]에 더해준다.
3. 보이는 건물 중 stack[-1], 즉 스택의 top에 있는 건물이 나(i)로부터 가까운 건물이다. 그런데 우리는 왼쪽, 오른쪽에서 한 번씩 탐색하므로 두 건물 중 더 가까운 건물이 ans[i][1]에 저장되도록 한다.
4. 현재 건물 i를 stack에 넣어준다.