알고리즘 문제는 코딩 테스트에서 매우 중요합니다. 특히 자바를 사용하여 문제를 해결하는 능력은
많은 기업에서 요구하는 스킬 중 하나입니다. 본 글에서는 “물의 양 구하기”라는 주제를 가지고
자세히 설명하겠습니다. 이 문제를 통해 알고리즘 해법을 찾고, 자바로 구현하는 과정을 단계별로
살펴보겠습니다.
문제 설명
여러분은 한 주어지는 높이의 배열을 가지고 있습니다. 각 인덱스는 블록을 나타내며, 인덱스의 값은
블록의 높이를 의미합니다. 이 배열에서 주어진 비에 의해 저장될 수 있는 물의 양을 계산하는
프로그램을 작성해야 합니다.
예를 들어, 주어진 배열이 [0, 1, 0, 2, 1, 0, 1, 3, 2, 1, 2, 1]이라면, 배열에서 저장되는
물의 양을 구해야 합니다.
문제 풀이 접근 방식
이 문제를 해결하기 위한 접근 방식은 여러 가지가 있지만, 가장 직관적인 방법은 두 포인터
접근법을 사용하는 것입니다. 두 포인터를 사용하여 배열의 양쪽 끝에서부터 중앙으로
이동하면서 각 인덱스에 저장될 수 있는 물의 양을 계산할 수 있습니다.
1단계: 문제 이해하기
인덱스마다 저장되는 물의 양은 해당 인덱스의 왼쪽과 오른쪽에서 가장 높은 블록의 높이에 의해
결정됩니다. 따라서 저장된 물의 양은
min(왼쪽 최대 높이, 오른쪽 최대 높이) - 현재 블록의 높이입니다. 만약 이 값이
음수라면 물이 저장되지 않으므로 0으로 설정할 수 있습니다.
2단계: 알고리즘 설계
알고리즘을 설계하기 위해 다음과 같은 단계를 설정합니다:
- 배열의 길이를 구하여 사용자에게 예외 처리합니다.
- 양쪽 끝에서 시작하여 두 포인터를 설정합니다.
- 각 포인터에서 최대 높이를 추적합니다.
- 두 포인터가 만날 때까지 반복합니다.
- 각 단계에서 저장된 물의 양을 계산합니다.
3단계: 코드 구현
이제 위의 설계를 바탕으로 자바 코드를 구현해 보겠습니다.
public class WaterTrapping {
public static int calculateWater(int[] height) {
if (height == null || height.length == 0) {
return 0;
}
int left = 0, right = height.length - 1;
int leftMax = 0, rightMax = 0;
int totalWater = 0;
while (left < right) {
if (height[left] < height[right]) {
if (height[left] >= leftMax) {
leftMax = height[left];
} else {
totalWater += leftMax - height[left];
}
left++;
} else {
if (height[right] >= rightMax) {
rightMax = height[right];
} else {
totalWater += rightMax - height[right];
}
right--;
}
}
return totalWater;
}
public static void main(String[] args) {
int[] height = {0, 1, 0, 2, 1, 0, 1, 3, 2, 1, 2, 1};
System.out.println("저장된 물의 양: " + calculateWater(height) + " 단위");
}
}
4단계: 코드 설명
위의 코드에서 핵심은 while (left < right) 루프입니다. 이 반복문은 두 포인터가
서로 교차할 때까지 계속해서 반복됩니다.
-
왼쪽 포인터가 오른쪽 포인터보다 작은 경우: 왼쪽의 최대 높이를 업데이트하거나,
현재 값이 낮으면 저장할 수 있는 물의 양을 계산합니다. -
오른쪽 포인터가 왼쪽 포인터보다 작은 경우: 오른쪽의 최대 높이를 업데이트하거나,
저장할 수 있는 물의 양을 계산합니다.
이렇게 하여 두 포인터가 만날 때까지 반복하면서 저장된 물의 양을 합산하게 됩니다.
결론
오늘은 “물의 양 구하기” 문제를 통해 코딩 테스트에서 자주 출제되는 알고리즘을 학습했습니다.
두 포인터를 사용하는 알고리즘은 효율적인 공간 활용과 시간 복잡도를 제공하기 때문에,
실제 코딩 테스트에서 많이 사용되므로 충분히 연습하시길 바랍니다.
다양한 추가적인 예제와 함께 복잡한 테스트 케이스를 통해 더욱 깊이 있는 학습을 이어가시길
바랍니다. 이 문제를 통해 알고리즘적 사고가 깊어지기를 희망합니다.