[LeetCode/Kotlin] 11. Container With Most Water

문제

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

 

풀이

• 부르트포스로 풀어보면 시간초과가 된다.
• 가장 왼쪽, 오른쪽 기둥을 시작점으로 잡고, 더 짧은 쪽은 안쪽으로 한 칸씩 이동하면서 넓이를 구해준다.
• 넓이를 구할 때마다 최대값을 저장

import kotlin.math.max
import kotlin.math.min

class Solution {
    fun maxArea(height: IntArray): Int {
        var answer: Int = 0
        // 가장 바깥쪽 기둥부터 탐색
        var left = 0
        var right = height.size - 1

        while(left < right) {
            val area: Int = (right - left) * min(height[left], height[right])
            answer = max(answer, area)

            // 왼쪽, 오른쪽 중 더 짧은 쪽을 안쪽으로 이동
            if(height[left] > height[right]) {
                right--
            }
            else {
                left++
            }
        }

        return answer
    }
}

 

< 실패한 풀이 >

// LeetCode - 11. Container With Most Water / Time Limit Exceeded
import kotlin.math.max
import kotlin.math.min

class Solution {
  fun maxArea(height: IntArray): Int {
    var answer: Int = 0
    
    for(i: Int in 0..(height.size - 2)) {
      for(j: Int in (i + 1)..(height.size - 1)) {
        val area: Int = (j-i) * min(height[i], height[j])
        answer = max(answer, area)
      }
    }

    return answer
  }
}