파이썬으로 전망이 좋은 건물 찾기: 배열 탐색 알고리즘 구현

문제 개요

여러 건물의 높이가 담긴 배열이 주어졌다고 가정해 보겠습니다. 건물들은 한 줄로 나란히 서 있으며, 어떤 건물의 시야가 그보다 높은 다른 건물에 가려지지 않는다면 해당 건물은 '전망이 좋은 건물'이라고 정의할 수 있습니다. 따라서 높이 정보가 담긴 배열이 주어졌을 때, 다른 더 높은 건물에 의해 시야가 막히지 않는 건물들을 찾아 조건을 만족하는 인덱스들을 반환해야 합니다.

예를 들어 입력이 height = [5, 6, 8, 7]이라면 출력은 [2, 3]이 됩니다. 인덱스 0과 1에 있는 건물(높이 5, 6)은 인덱스 2의 더 높은 건물(높이 8)에 가려져 전망이 좋지 않습니다. 반면 인덱스 2와 3의 건물은 가려지지 않는데, 인덱스 2의 높은 건물은 바로 옆 인덱스 3의 낮은 건물(높이 7) 위로 시야가 확보되기 때문입니다.

해결 접근 방법

이 문제는 배열을 오른쪽에서 왼쪽으로 순회하면 효율적으로 해결할 수 있습니다. 오른쪽 끝부터 살펴보면서 지금까지 확인한 건물 중 가장 높은 값을 기록하고, 현재 건물이 그 값보다 높다면 전망이 좋은 건물이므로 결과 목록에 추가하는 방식입니다.

구체적인 단계는 다음과 같습니다.

• res := 결과를 저장할 새로운 리스트
• h := 지금까지 확인한 최대 높이 (초깃값 0)
• i를 len(heights) - 1부터 0까지 1씩 감소시키며 반복:
  • 만약 heights[i] > h 이면:
    • res의 끝에 i를 추가
    • h := heights[i] 로 갱신
• 반복이 끝나면 res를 뒤집어 반환 (왼쪽 → 오른쪽 순서 유지)

구현 예제

아래 파이썬 코드를 통해 실제 동작을 확인해 보겠습니다.

def solve(heights):
    res, h = [], 0
    for i in range(len(heights) - 1, -1, -1):
        if heights[i] > h:
            res.append(i)
            h = heights[i]
    return res[::-1]

print(solve([5, 6, 8, 7]))

입력

[5, 6, 8, 7]

출력

[2, 3]

복잡도 분석

이 알고리즘은 배열을 한 번만 순회하므로 시간 복잡도는 O(n)입니다. 추가로 사용하는 공간은 결과 리스트와 최대 높이 변수 하나뿐이므로 공간 복잡도 역시 O(n)으로 매우 효율적입니다. 스택 기반 사고방식으로 오른쪽부터 스캔하면 불필요한 비교 없이 선형 시간 안에 답을 구할 수 있다는 점이 핵심입니다.