11. Container With Most Water

hs·2021년 8월 28일
4

Leetcode

목록 보기
1/4

🎰 문제

문제는 다음과 같다. 인자로 주어지는 height값은 숫자들로 이루어진 배열이고 그래프에서 y축(높이)를 나타내고 있다.

위와 같은 배열을 그래프로 옮겼을 경우 물을 담을 수 있는 가장 넓은 면적의 넓비 값을 반환해 주세요.

🧩 생각 1

그림과 같은 예시의 배열은 [1, 8, 6, 2, 5, 4, 8, 3, 7]이다. 제일 처음으로 한 생각은 이중 for문의 형식으로 배열의 첫번째 인덱스를 반복문을 돌게한 후, 그 내부에서 하나씩 다음 인덱스부터 인덱스 값을 1씩 증가해간다. 모든 경우의 수를 다 통과해가며 그 값을 max()를 통해 비교해가며 저장을 하여 최대값을 구하는 방법이였다.

  1. 가장 큰 고정 인덱스
  2. 고정 인덱스 다음 인덱스부터 차례차례 1씩 증가시키며 비교
  3. 인덱스 값이 증가 할때 마다 넓이값을 구해 max()를 통해 비교
1
2
3
4
5
6
7
8
9
10
11
class Solution:
    def maxArea(self, height: List[int]) -> int:
          result = 0  # 각각의 넓이값
          max_value = 0  # 최대값 리턴
  
          for i in range(len(height)):
               for j in range(len(height)):
                  result = (j-i) * min(height[i],height[j]) # 넓이 구하는 식
                  max_value = max(max_value, result) # max값 
                
           return max_value
cs

위와 같은 코드가 나온다.

❌ 생각 1의 문제점

위와 같이 작성하면 결과값은 일치하게 나오지만 for문이 두번 사용되었기 때문에 시간 복잡도가 O(n^2)로 제곱의 형태로 나와 좋지 못하였다.

🧩 생각 2

그러다 생각이 난 것이 전에 얼핏 들었었던 양 쪽 끝점부터의 비교였다. 쉽게 정리하자면 0번 인덱스와 마지막 인덱스의 값을 초기값으로 잡고 비교해 나가는 방식이다.

  1. 양 쪽 끝 인덱스를 초기값으로 저장
  2. 그 사이의 넓이 값을 구한다.
  3. 양 쪽 값을 비교하여 왼쪽이 작으면 하나 증가시키고 오른쪽이 작으면 하나 감소시킨다.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
class Solution:
    def maxArea(self, height: List[int]) -> int:
      i, j = 0,len(height)-1
      m = 0
      result = 0
      while i != j:
        result = (j-i) * (min(height[i],height[j]))
        if height[i] < height[j]:
          i += 1
        else:
          j -= 1
 
        m = max(m, result)
 
      return m
cs

🎯 해결

위와 같이 진행하면 반복문을 한번만 사용해서 진행할 수 있다. 반복문을 무조건적으로 for문이 아닌 while문을 사용할 수도 있고 상황에 따라서 알맞게 사용하는 것이 맞는거 같다. 여기서 사용하는 알고리즘은 two point 알고리즘이라고 부른다. 간단하게 설명하자면 양쪽부터 시작해가며 비교해가며 하나하나 줄여나아가는 방식이다.

profile
무엇이든 끝까지 보람차게

2개의 댓글

comment-user-thumbnail
2021년 8월 29일

코드카타의 신 현수님!! 이렇게 문제 정리도 하시고!! 현수님의 아이디어에 감탄을 많이 합니다ㅎㅎ

1개의 답글