[백준] 탑 보기

https://www.acmicpc.net/problem/22866

22866번: 탑 보기

스택을 이용하면 풀 수 있는 문제입니다. 빗물문제와 비슷해서 풀이법을 비교적 쉽게 떠올릴 수 있었습니다. 해당 문제를 풀으신 분들은 빗물문제도 도전해보시면 좋을 것 같습니다. 왼쪽 -> 오른쪽, 오른쪽 -> 왼쪽으로 탐색하면서 본인보다 작은 건물들을 스택에서 제거해주면됩니다. 

 

왼쪽 -> 오른쪽을 예시로 설명드리겠습니다. 왼쪽에서 오른쪽으로 탐색하면서 스택에는 빌딩들의 인덱스를 저장하게 됩니다. 스택에서 본인보다 높이가 높은 빌딩을 만날 때까지 스택에서 pop해줍니다. 더이상 pop이 불가능하다면 stack에 남아있는 빌딩들이 현재 본인보다 왼쪽에 있는 빌딩들 중 현재 빌딩보다 높이가 높은 빌딩들이 남게 됩니다. 따라서, 현재 스택에 남아있는 빌딩들의 개수가 곧 왼쪽 방향을 바라봤을 때 볼 수 있는 빌딩들의 수가 되고 스택의 top에 있는 빌딩이 가장 가까운 볼 수 있는 빌딩이 됩니다. 이 과정을 마찬가지로 오른쪽 -> 왼쪽 방향으로도 수행해주면 답을 구할 수 있습니다.

 

 

# 문제링크: https://www.acmicpc.net/problem/22866
import sys

# sys.stdin = open("input.txt", "r")

input = sys.stdin.readline
INT_MAX = sys.maxsize

# 건물의 개수
n = int(input())

# 빌딩의 높이들
buildings = list(map(int, input().split()))

# 각 빌딩에서 볼 수 있는 빌딩의 숫자
building_count = [0] * n

# 볼 수 있는 건물중 가장 가까운 빌딩
near_building = [INT_MAX] * n

# 왼쪽 -> 오른쪽으로 탐색하면서 현재 빌딩의 높이보다 큰 빌딩들은 담는 stack
left_stack = []

for i, height in enumerate(buildings):
    # 스택에 요소들이 있고 현재 높이보다 낮은 빌딩들은 모두 제거
    while left_stack and buildings[left_stack[-1]] <= height:
        left_stack.pop()

    building_count[i] += len(left_stack)

    # 가장 가까이에 있는 빌딩 갱신
    if left_stack:
        if abs(i - left_stack[-1]) < abs(near_building[i] - i):
            near_building[i] = left_stack[-1]

    left_stack.append(i)

# 오른쪽 -> 왼쪽으로 탐색하면서 현재 빌딩의 높이보다 큰 빌딩을 담는 스택
right_stack = []

for i in range(n - 1, -1, -1):
    height = buildings[i]
    
    # 스택에 요소들이 있고 현재 높이보다 낮은 빌딩들은 모두 제거
    while right_stack and buildings[right_stack[-1]] <= height:
        right_stack.pop()

    building_count[i] += len(right_stack)

    # 가장 가까이에 있는 빌딩 갱신
    if right_stack:
        if abs(i - right_stack[-1]) < abs(near_building[i] - i):
            near_building[i] = right_stack[-1]

    right_stack.append(i)

for i in range(n):
    # 볼 수 있는 빌딩이 있는 경우
    if building_count[i]:
        print(building_count[i], near_building[i] + 1)
    else:
        print(0)