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

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

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

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

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

입력

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

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

출력

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

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

풀이 아이디어

풀이 아이디어를 2가지 키워드로 표현하면 '스택, 문워크'이다.
오른쪽으로 이동하며 왼쪽 도시를 확인한다.
문워크하며 확인한다고 보면 된다.
스택에 (도시 높이, 도시 인덱스)를 담는다.

1. 스택 맨 위를 확인하고 현재 높이보다 높은 높이가 나올 때까지 pop
2. 높은 높이가 나오면 종료하고 스택의 크기 만큼 count를 증가한다.
   스택의 크기는 현재 도시 기준으로 높은 볼 수 있는 도시 수를 의미한다.
3. 이후 볼 수 있는 최소 인덱스를 갱신한다.
4. 현재 도시의 높이와 인덱스를 스택에 push
5. 마지막에 좌우의 볼 수 있는 도시의 수를 합하고 거리가 가까운 최소 인덱스를 출력한다.

트러블슈팅

정답 출력에서 "거리가 가장 가까운 건물의 번호 중 작은 번호"를 출력하는 부분이 있는데
처음에는 왼쪽 문워크와 오른쪽 문워크로 확인한 인덱스 중 최솟값을 줬다.

minViewIndex = min(minLeftViewIndex[i],minRightViewIndex[i])

근데 이렇게 구현하면 아래와 같은 경우 잘못된 출력을 하게 되었다.

거리는 멀지만 인덱스가 작은 것을 출력해서 잘못된 답을 출력하게 되었다.
그래서 아래처럼 거리로 먼저 최소 인덱스를 구하고
만약 i-1, i, i+1처럼 같은 거리로 떨어진 경우에는
i-1인 인덱스를 출력하도록 프로그램을 작성했다.

if (abs(i-minLeftViewIndex[i]) < abs(i-minRightViewIndex[i])):
        minViewIndex = minLeftViewIndex[i]
    elif (abs(i-minLeftViewIndex[i]) > abs(i-minRightViewIndex[i])):
        minViewIndex = minRightViewIndex[i]
    else:
        minViewIndex = min(minLeftViewIndex[i],minRightViewIndex[i])

풀이 코드

import sys
input = sys.stdin.readline

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

# 볼 수 있는 건물의 수 확인
leftStack = [] 
leftCount = [0]*(n+1) # 왼쪽을 본 수
minLeftViewIndex = [float('inf')]*(n+1)

rightStack = []
rightCount = [0]*(n+1)
minRightViewIndex = [float('inf')]*(n+1)

# 오른쪽으로 문워크하면서 왼쪽 확인
leftStack.append((city_height[1],1))
for i in range(2,n+1):
    stackTopHeight = leftStack[-1][0]
    currentHeight = city_height[i]
    # peek로 맨 위를 확인해 현재 높이보다 높은 높이가 나올때까지 pop
    while currentHeight >= stackTopHeight:
        leftStack.pop()
        if len(leftStack)!=0:
            stackTopHeight = leftStack[-1][0]
        elif len(leftStack)==0:
            break
    # 높은 높이가 나오면 Stack.size만큼 count 증가
    leftCount[i]+=len(leftStack)

    # 볼 수 있는 최소 인덱스 갱신
    if len(leftStack)!=0:
        minLeftViewIndex[i] = min(minLeftViewIndex[i], leftStack[-1][1])

    # 현재 높이를 Stack에 push
    leftStack.append((currentHeight,i))
    
    
# 왼쪽으로 문워크하면서 오른쪽 확인
rightStack.append((city_height[-1],n))
for i in reversed(range(1,n)):
    stackTopHeight = rightStack[-1][0]
    currentHeight = city_height[i]
    # peek로 맨 위를 확인해 현재 높이보다 높은 높이가 나올때까지 pop
    while currentHeight >= stackTopHeight:
        rightStack.pop()
        if len(rightStack)!=0:
            stackTopHeight = rightStack[-1][0]
        elif len(rightStack)==0:
            break
    # 높은 높이가 나오면 Stack.size만큼 count 증가
    rightCount[i]+=len(rightStack)

    # 볼 수 있는 최소 인덱스 갱신
    if len(rightStack)!=0:
        minRightViewIndex[i] = min(minRightViewIndex[i], rightStack[-1][1])

    # 현재 높이를 Stack에 push
    rightStack.append((currentHeight,i))

# 결과 출력 
for i in range(1,n+1):
    sumView = leftCount[i]+rightCount[i]
    # 인덱스 다시 처리하기 
    if (abs(i-minLeftViewIndex[i]) < abs(i-minRightViewIndex[i])):
        minViewIndex = minLeftViewIndex[i]
    elif (abs(i-minLeftViewIndex[i]) > abs(i-minRightViewIndex[i])):
        minViewIndex = minRightViewIndex[i]
    else:
        minViewIndex = min(minLeftViewIndex[i],minRightViewIndex[i])
    
    if sumView==0:
        print(sumView)
    else:
        print(sumView, minViewIndex)