[leetcode 11] Container With Most Water

11. Container With Most Water

https://leetcode.com/problems/container-with-most-water/

해결 과정

idx 사이의 거리, array의 두 index에 해당하는 값 중 작은 값, 그리고 이들을 곱한 넓이 들 중 최대 값을 구했다.

코드1

  • 2중 for문을 사용하여 전체 케이스를 검사하기때문에 time complexity 면에서 아쉬운 풀이.
fun maxArea(height: IntArray): Int {
    val size = height.size
    var area = 0
    var max = 0
        
    height.forEachIndexed { i, item ->
        for(j in i until size) {
            area = (j-i) * minOf(item, height[j])
            max = maxOf(max, area)
        }    
    }
    return max
}

코드2

  • # Two Pointers 를 사용하여 개선한 코드.
fun maxArea(height: IntArray): Int {
    var left = 0
    var right = height.size - 1
    var area = 0
    var max = 0

    while(left < right) {
        area = (right-left) * minOf(height[left], height[right])
        max = maxOf(max, area)
            
        if(height[left] < height[right]) {
            left++
        } else {
            right--
        }
    }
    return max
}

배운 점

  • Two Pointers 로 풀 수 있는 문제인지 생각해보자.
  • 2중 for문을 사용한 풀이를 개선할 수 있을지 고민해보자.

Leave a comment