[백준] 22866번 - 탑 보기 Python

문제

---

일직선으로 다양한 높이의 건물이 총 $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$번째 건물에서 거리가 가장 가까운 건물의 번호 중 작은 번호로 출력한다.

제한

---

•  $1 \le N \le 100,000$ 
• $1 \le L \le 100,000$ 

예제 입력 1

---

8
3 7 1 6 3 5 1 7

예제 출력 1

---

1 2
0
3 2
2 2
4 4
3 4
4 6
0

풀이

---

import sys

input = sys.stdin.readline

n = int(input().rstrip())
l = list(map(int,input().rstrip().split()))

stack = []
cnt = [0]*(n+1)
near = [[int(1e9),int(1e9)] for _ in range(n+1)]

for idx, v in enumerate(l):
    while len(stack)>0 and stack[-1][1] <= v:
        stack.pop()
    cnt[idx+1] += len(stack)
    
    if len(stack) > 0 :
        g = abs(stack[-1][0] - (idx+1))
        if g < near[idx+1][1]:
            near[idx+1][0] = stack[-1][0]
            near[idx+1][1] = g
        elif g == near[idx+1][1] and stack[-1][0] < near[idx+1][0]:
            near[idx+1][0] = stack[-1][0]
    stack.append([idx+1,v])

stack = []
for idx,v in reversed(list(enumerate(l))):
    while len(stack) >0 and stack[-1][1] <=v:
        stack.pop()
    cnt[idx+1] += len(stack)

    if len(stack) > 0 :
        g = abs(stack[-1][0] - (idx+1))
        if g < near[idx+1][1]:
            near[idx+1][0] = stack[-1][0]
            near[idx+1][1] = g
        elif g == near[idx+1][1] and stack[-1][0] < near[idx+1][0]:
            near[idx+1][0] = stack[-1][0]
    stack.append([idx+1,v])

for i in range(1,n+1):
    if cnt[i]>0:
        print(str(cnt[i])+' '+str(near[i][0]))
    else:
        print(0)

정리

---

• 각 건물에서 좌측, 위측으로 보이는 건물의 개수를 세어주고 각 건물에서 가장 가까운 건물 번호 중 작은 번호를 출력한다.
• near배열은 near[a][0]의 경우 a 건물에서 가장 가까운 건물 번호를 나타내며, near[a][1]의 경우에는 가장 가가운 건물의 거리를 나타내는 배열이다.
• monotone stack을 이용해 단조감소 하도록 구현 하였고, 현재 stack에 저장된 값들은 현재 건물에서 좌측 혹은 우측으로 보이는 건물들의 수이고, stack의 마지막 값은 가장 가까운 건물이다.