BOJ 22866

🖋️ 문제

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

💻 내 코드

# 22866

import sys
input = sys.stdin.readline

n = int(input())
arr = list(map(int, input().split()))

left_index = [] # 
left = [[0, -1000000] for _ in range(n)]
for i in range(n):
    if left_index:
        while left_index:
            if arr[left_index[-1]] <= arr[i]:
                left_index.pop()
            else:
                break
        if len(left_index):
            left[i] = (len(left_index), left_index[-1])
        left_index.append(i)
    else:
        left_index.append(i)

right_index = []
right = [[0, 1000000] for _ in range(n)]
for i in range(n-1, -1, -1):
    if right_index:
        while right_index:
            if arr[right_index[-1]] <= arr[i]:
                right_index.pop()
            else:
                break
        if len(right_index):
            right[i] = (len(right_index), right_index[-1])
        right_index.append(i)
    else:
        right_index.append(i)

for i in range(n):
    num = left[i][0]+right[i][0]
    if num == 0:
        print(0)
        continue
    if (i - left[i][1]) <= (right[i][1]-i):
        index = left[i][1]
    else:
        index = right[i][1]
    print(num, index + 1)

자료의 크기와 문제의 난의도를 고려했을 때 절대로 모든 건물에 대해서 하나하나 좌우로 보이는 건물 수를 세는 빡구현 문제는 아닐 것이라고 생각했다. 그래서 우선 좌측으로 보이는 건물들을 O(n)시간으로 구하고 오른쪽도 마찬가지로 구한 다음 좌우측을 더하고 비교해서 보이는 건물의 개수와 가까운 건물의 번호를 구하였다.

즉, 이 문제의 핵심은 임의의 건물에 대하여 어느 한 방향에서 보이는 건물들을 상수시간을 들여 업데이트해 나가는 것이다.

👍 제출

처음에 시간초과가 난 이유는 각 방향에 대해 보이는 건물 중 가까운 건물의 인덱스값을 저장하는 과정에서 min, max 함수를 사용하였기 때문이었다. 시간복잡도가 O(n)인 함수를 포문 안에서 무심코 써버렸다... 간단하게 left_index[-1]로 수정하여 정답을 받을 수 있었다.