문제 정의
여러 건물의 높이가 담긴 리스트가 주어졌다고 가정해 보겠습니다. 이때 특정 건물이 바다를 볼 수 있는 조건은, 그 건물의 오른쪽에 있는 모든 건물이 자신보다 낮을 때입니다. 우리의 목표는 바다가 보이는 건물들의 인덱스를 오름차순으로 찾아내는 것입니다.
예를 들어 입력이 다음과 같다면,
[8, 12, 12, 9, 10, 6]
출력은 [2, 4, 5]가 됩니다. 인덱스 2(높이 12), 인덱스 4(높이 10), 그리고 마지막 건물인 인덱스 5(높이 6)에서 바다가 보이기 때문입니다.
접근 방법: 스택(Stack) 활용
이 문제는 스택 자료구조를 사용하면 효율적으로 해결할 수 있습니다. 핵심 아이디어는 다음과 같습니다.
- 빈 스택을 준비합니다.
- 건물 높이 리스트를 왼쪽부터 순회하면서, 현재 건물과 높이가 같거나 더 낮은 건물(스택의 맨 위 요소)을 모두 제거합니다. 이러한 건물들은 오른쪽에 자신보다 높거나 같은 건물이 존재하므로 바다를 볼 수 없기 때문입니다.
- 현재 건물의 인덱스를 스택에 추가(push)합니다.
- 모든 순회가 끝나면 스택에는 바다가 보이는 건물의 인덱스만 남게 됩니다.
알고리즘 단계
stack:= 새로운 빈 리스트 생성- heights의 각 인덱스(idx)와 높이(h)에 대해 반복:
- 스택이 비어 있지 않고
heights[스택 맨 위]<= h인 동안, 스택의 마지막 요소를 삭제(pop)
- 스택이 비어 있지 않고
- idx를 스택에 push
- 스택 반환
파이썬 구현 예제
다음 코드를 통해 실제 동작을 확인해 보겠습니다.
def solve(heights):
stack = []
for idx, h in enumerate(heights):
while stack and heights[stack[-1]] <= h:
stack.pop()
stack.append(idx)
return stack
heights = [8, 12, 12, 9, 10, 6]
print(solve(heights))
입력
[8, 12, 12, 9, 10, 6]
출력
[2, 4, 5]
동작 과정 상세 분석
- idx 0 (높이 8): 스택이 비어 있으므로 push → [0]
- idx 1 (높이 12): heights[0]=8 ≤ 12이므로 pop 후 push → [1]
- idx 2 (높이 12): heights[1]=12 ≤ 12이므로 pop 후 push → [2]
- idx 3 (높이 9): heights[2]=12 > 9이므로 그대로 push → [2, 3]
- idx 4 (높이 10): heights[3]=9 ≤ 10이므로 pop, heights[2]=12 > 10이므로 중단 후 push → [2, 4]
- idx 5 (높이 6): heights[4]=10 > 6이므로 그대로 push → [2, 4, 5]
복잡도 분석
각 인덱스는 최대 한 번 push되고 한 번 pop되므로 전체 시간 복잡도는 O(n)입니다. 단순히 매 건물마다 오른쪽을 모두 확인하는 브루트 포스 방식(O(n²))보다 훨씬 효율적입니다. 공간 복잡도는 최악의 경우(높이가 계속 감소하는 경우) 모든 인덱스가 스택에 저장될 수 있으므로 O(n)입니다.