LeetCode - The World's Leading Online Programming Learning Platform

Problem

1. input: 선들의 높이가 저장된 height

2. output: 두 선으로 만들 수 있는 직사각형의 넓이의 최댓값 리턴

3. 직사각형의 높이는 두 선의 높이 중 더 낮은 높이

   

   • n == height.length
   • 2 <= n <= 10^5
   • 0 <= height[i] <= 10^4

Idea

특정 조건을 만족하는 구간 찾기 문제 + 이중 for문 완전탐색으로 답을 찾을 수 있는 문제 = 투 포인터 문제

사실 풀어본 적 있는 전형적인 투포인터 문제라서 투포인터로 풀면 통과 된다. → Sol1

이중 for문 완전탐색으로 답은 구할 수 있지만 배열의 길이가 10^5 이기 때문에 이중 for문을 쓰면 최악의 경우 10^10(10억)이어서 시간초과가 날 것이다. 확인 → Sol2

보통 알고리즘 시간 제한이 1초, 연산 1억회로 계산했기에, 완전 탐색을 조금만 발전시켜 통과되는 지 확인해 보았다.

넓이의 최댓값을 구하는 것이기 때문에 한쪽 끝에서 반대쪽 끝으로 이동하며, 이전의 최대 높이보다 높은 선이 나왔을 때만 높이를 확인하면 된다. 이를 이용하여 넓이를 확인할 점들을 미리 간추리고 이중 for문으로 완전 탐색할 경우, 최악의 경우 5e4 * 5e4 = 2.5e9.

2억회라서 아슬아슬하게 통과할 수도 있을 것 같아 확인해보니 통과는 됐다ㅋㅋ → Sol3

Solution

1. 투포인터

   • 높이가 더 낮은 쪽의 커서를 한칸 이동
   • 넓이 갱신

   class Solution {
       fun maxArea(height: IntArray): Int {
           var answer = 0
           var left = 0
           var right = height.size - 1
           while(left < right) {
               // 넓이 갱신
               answer = maxOf(answer, (minOf(height[left], height[right]) * (right - left)))
               if (height[left] <= height[right]) {
                   left++
               } else {
                   right--
               }
           }
           return answer
       }
   }
   

   시간 복잡도: 배열 순회 = n

   

2. 완전탐색 → 시간 초과

   가능한 모든 경우에 대해 넓이 갱신

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

   시간 복잡도: 구간 완전 탐색 = n^2

   → 최악의 경우 = 1.0e10

3. 최댓값이 갱신되는 지점만 탐색

   • 좌→우, 우→좌, 진행 방향에서 height의 최댓값이 갱신되는 지점만 저장

     → 정답이 될 수 있는 후보를 미리 추출

   • 위에서 저장한 지점에 대해서만 탐색

   class Solution {
       fun maxArea(height: IntArray): Int {
           var answer = 0
           // 한쪽 끝에서 반대쪽 끝으로 진행하며 최댓값이 갱신되는 지점 저장
           var leftMax = mutableListOf<IntArray>()
           var rightMax = mutableListOf<IntArray>()
           var tmpLeft = -1
           var tmpRight = -1
           for (i in height.indices) {
               if (tmpLeft < height[i]) {
                   tmpLeft = height[i]
                   leftMax.add(intArrayOf(i, tmpLeft))
               }
               if (tmpRight < height[height.size - 1 - i]) {
                   tmpRight = height[height.size - 1 - i]
                   rightMax.add(intArrayOf(height.size - 1 - i, tmpRight))
               }
           }
           // 위에서 저장한 최댓값이 갱신되는 지점에 대해서만 넓이 확인
           for (i in leftMax) {
               for (j in rightMax) {
                   answer = Math.max(answer, (Math.min(i[1], j[1]) * (j[0] - i[0])))
               }
           }
           return answer
       }
   }
   

   시간 복잡도: 배열 탐색(최댓값 갱신 지점 찾기) + 완전탐색 = n^2 → 최악의 경우 = 2.5e9

   

Point

1. 배열에서 조건을 만족하는 구간 찾기 + 완전탐색으로 무조건 풀 수 있는 문제 ⇒ 투포인터