문제풀이/자료구조

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

딜레이레이 2023. 11. 21. 19:11
 

22866번: 탑 보기

3번째 건물에서 볼 수 있는 건물은 2, 4, 8번째 건물로 총 3개를 볼 수 있다. 그 중 3번째 건물과 가장 가까운 건물은 2, 4번째 있는 건물로 이 중 번호가 작은 번호인 2가 답이 된다.

www.acmicpc.net

 

문제

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

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

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

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

번호 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

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



입력

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

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



출력

번째 건물에서 볼 수 있는 건물의 개수를 출력한다.

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



코드

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에 넣어준다.