(Leetcode)11.Container with most water
[LeetCode] 11.Container with most water
문제
주어진 숫자의 그래프에서 물을 채울 수 있는 최대 넓이를 구하시오. You are given an integer array height of length n. There are n vertical lines drawn such that the two endpoints of the ith line are (i, 0) and (i, height[i]).
Find two lines that together with the x-axis form a container, such that the container contains the most water.
Return the maximum amount of water a container can store.
Notice that you may not slant the container.
첫번째 풀이
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
func maxArea(height []int) int {
var maxSpace int
for i := 0; i < len(height); i++ {
for j := i + 1; j < len(height); j++ {
space := 0
if height[i] > height[j] {
space = height[j] * (j - i)
} else {
space = height[i] * (j - i)
}
if space > maxSpace {
maxSpace = space
}
}
}
return maxSpace
}
우선 이 문제에서 생각해두어야 할 것은
- 기준점이 되는 Pivot 보다 낮은 height의 수가 나타날 경우 그 작은 수가 Pivot을 대체해야 한다.
- 어떻게 효율적으로 순회할지 생각해봐야 한다.
일단 처음 풀이에서는 2번째 사항은 고려 안하고 우선 모든 값에 대하여 이중 순회를 돌아보았다. 1의 원칙에 따라 Pivot을 구하고 index의 차이에 따라 물의 넓이를 구하였다.
그리고 간단하게 넓이의 최댓값을 갱신하는 것으로 문제를 풀어보았다.
이 결과 테스트 케이스는 모두 통과하지만, 무지막지하게 긴 input이 주어질 경우 Time Exceed error가 나타나는 것을 확인 할 수 있었다.
두번째 풀이
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
func maxArea(height []int) int {
var maxSpace int
lt := 0
rt := len(height) - 1
for lt < rt {
diff := rt - lt
minHeight := 0
if height[lt] < height[rt] {
minHeight = height[lt]
} else {
minHeight = height[rt]
}
space := minHeight * diff
if space > maxSpace {
maxSpace = space
}
if minHeight == height[lt] {
lt++
} else {
rt--
}
}
return maxSpace
}
이 방법에서는 Two pointer method를 적용시켜 보았다. 왼쪽 오른쪽 인덱스의 값이 비교하여 값이 작은 쪽을 포인터를 옮겨주는 방식으로 순회를 한다. 이렇게 푸니 아슬아슬하게 제한시간을 넘겨 풀이에 성공했다.
느낀점
처음엔 당황스러웠는데 생각보다 풀만했던 문제!