코딩 테스트에서 자주 출제되는 문제 중 하나는 특정 조건을 만족하는 “물의 양”을 구하는 문제입니다. 이번 강좌에서는 이를 통해 파이썬 코드를 작성하는 방법과 알고리즘적 사고의 중요성에 대해 알려드리겠습니다.
문제 설명
여러분은 한개의 수조에서 물의 양을 계산해야 합니다. 수조의 높이를 나타내는 정수 배열 height가 주어졌습니다. 수조는 수평으로 배열된 블록으로 구성되어 있으며, 각 블록의 높이는 height[i]로 표현됩니다.
비가 내린 후, 각 블록 사이에 고인 물의 양을 계산하는 함수를 만들고, 총 고인 물의 양을 반환해야 합니다.
입력
height: 양의 정수로 이루어진 리스트. (1 ≤ height.length ≤ 2 * 10^4, 0 ≤ height[i] ≤ 10^5)
출력
- 고인 물의 총 양을 나타내는 정수
예제
예제 1
입력: height = [0,1,0,2,1,0,1,3,2,1,2,1]
출력: 6설명: 고인 물의 양은 6입니다.
예제 2
입력: height = [4,2,0,3,2,5]
출력: 9설명: 고인 물의 양은 9입니다.
문제 해결 접근법
문제를 해결하기 위해서는 두 가지 주요 포인트를 이해해야 합니다:
- 어떤 위치 i에서 고인 물의 양을 계산하기 위해서는 i 위치의 좌우 최대 높이를 알아야 합니다.
- 각 위치에서 고인 물의 양은
min(왼쪽 최대 높이, 오른쪽 최대 높이) - 현재 높이로 계산할 수 있습니다.
이를 위해 우리는 두 개의 배열을 생성할 것입니다. 하나는 왼쪽에서부터 각 위치의 최대 높이를 저장하고, 다른 하나는 오른쪽은 최대 높이를 저장합니다.
코드 구현
이제 이를 바탕으로 실제 코드를 작성해보겠습니다.
def trap(height):
if not height:
return 0
n = len(height)
left_max = [0] * n
right_max = [0] * n
# 왼쪽 최대 높이 계산
left_max[0] = height[0]
for i in range(1, n):
left_max[i] = max(left_max[i - 1], height[i])
# 오른쪽 최대 높이 계산
right_max[n - 1] = height[n - 1]
for i in range(n - 2, -1, -1):
right_max[i] = max(right_max[i + 1], height[i])
# 고인 물의 양 계산
water_trapped = 0
for i in range(n):
water_trapped += min(left_max[i], right_max[i]) - height[i]
return water_trapped
# 예제 실행
print(trap([0, 1, 0, 2, 1, 0, 1, 3, 2, 1, 2, 1])) # 출력: 6
print(trap([4, 2, 0, 3, 2, 5])) # 출력: 9
코드 설명
1. trap(height): 이 함수에서는 물을 trap(포획)하는 양을 계산합니다.
2. 입력으로 height 리스트를 받고, 이를 통해 물의 양을 계산합니다.
3. 빈 리스트인 경우 0을 반환합니다.
4. 각 인덱스에서 왼쪽 최대 높이를 계산하고, 오른쪽 최대 높이를 계산합니다.
5. 마지막으로 각 위치에서 저장된 최대 높이와 현재 높이를 통해 고인 물의 양을 계산합니다.
시간 복잡도 분석
이 알고리즘의 시간 복잡도는 O(n)입니다. 두 개의 배열을 만들어 각각의 최대 높이를 계산하는 데 O(n) 시간이 소요되며, 다시 반복적으로 고인 물의 양을 측정하는 데 O(n) 시간이 필요합니다.
모든 단계를 합치면 총 O(n)입니다.
결론
이번 강좌에서는 물의 양을 구하는 문제에 대해 심도 있게 학습해보았습니다. 이 문제는 알고리즘 문제 풀이의 대표적인 예로, 다양한 변형이 존재합니다. 여러분들도 이와 유사한 문제를 연습하면서 코드 작성 능력을 향상시키기 바랍니다.
추가 연습 문제
다음과 같은 변형 문제를 연습해보는 것을 추천합니다:
- 주어진 높이 배열에서 가장 많은 물이 고이는 위치는 어디인지 구하기
- 비가 내리지 않는 경우, 즉 모든 위치의 높이가 같은 경우를 처리하기
- 물의 흐름이 있을 때(즉, 각 블록의 물이 인접한 블록으로 흘러갈 수 있을 때) 어떻게 변화하는지 분석하기