Problem: Container With Most Water (Two-Pointer)

# Description

You are given an integer array height of length n. There are n vertical lines drawn such that the two endpoints of the i^th 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.

Example 1:

• Input: height = [1, 8, 6, 2, 5, 4, 8, 3, 7]
• Output: 49
• Explanation: The above vertical lines are represented by the array [1,8,6,2,5,4,8,3,7]. In this case, the max area of water the container can contain is 49. (The optimal container is formed by the lines at index 1 with height 8, and index 8 with height 7. The distance between them is 7. The height of the water is limited by the shorter line, which is 7. Thus, the area is 7 x 7 = 49.)

Example 2:

• Input: height = [1, 1]
• Output: 1

Constraints:

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

---

# Key Points

이 문제의 포인트는 가장 많은 물을 담을 수 있는 두 막대기를 골라서 최대 넓이를 구하는 것이다. 그렇기에 막대기들을 비교해 나가며 답을 찾아내야 한다는 것인데, 바로 이 점이 이 문제의 핵심이다. 이 문제에서 물어보는 결론은 바로 two-pointer (right-left)에 대해서 알고 있냐는 것이다. 만약에 효율을 중시안해도 된다면 당연히 2중 for문을 통해서 O(N^2)을 해도 되겠지만 효율을 높이기 위해서는 Time complexity가 O(N)이 되도록 유지할 수 있다. 그래서 이 문제의 key point는 두 개의 포인터를 두고 비교해 가며 결과를 산출해 낼 수 있는지이고 거기에 추가로 시간 효율성까지 고려하면 좋다.

---

# Solutions

Two-pointer를 쓸때는 가장 먼저 해야 하는 게 바로 최대 가로길이부터 확보하는 것이다. 그냥 쉽게 말해서 left=0, right = len(height)-1를 설정해두라는 것이다. 여기 문제에 맞게 height를 쓰지만 다른 문제에서는 그에 맞는 변수명을 넣어주면 된다. 그래서 두 포인터가 중앙으로 좁혀오면서 비교하는 문제가 나온다면 이 방식을 기억해 뒀다가 적용하면 되는 단순한 문제이다. 그리고 둘 중 어느 포인터를 움직여야 할까에 대해서는 당연히 더 짧은 값을 가리키는 포인터를 안쪽으로 이동시킨다. 여기서는 짧은 막대기가 해당된다.

---

class Solution:
    def maxArea(self, height: list[int]) -> int:
        # 1. 투 포인터 초기화 (맨 앞과 맨 뒤)
        left = 0
        right = len(height) - 1
        
        max_water = 0
        
        # 2. 두 포인터가 만날 때까지 반복
        while left < right:
            # 현재 두 막대기로 만들 수 있는 물의 넓이 계산
            current_width = right - left
            current_height = min(height[left], height[right])
            current_water = current_width * current_height
            
            # 최대 넓이 갱신
            max_water = max(max_water, current_water)
            
            # 3. 핵심 로직: 더 짧은 막대기 쪽의 포인터를 안쪽으로 이동
            if height[left] < height[right]:
                left += 1
            else:
                right -= 1
                
        return max_water

---

# Appendix

A word is defined as a sequence of nospace characters. The words in s will be separated by at least one space. Return a string of the words in reverse order concatenated by a single space.

 

추가로 위와 같은 단어로 순서를 뒤집는 문제가 나온다면, 이 역시도 two-pointer에 대해서 알고 있는지를 물어보기 위한 문제가 맞다. 다만 파이썬에서는 이에 맞는 methods가 존재하기에 한줄로 해결이 가능하다. 바로 join()와 split()이다. 아래 예제 코드처럼 split() methods를 통해서 단어만 리스트로 추출이 가능하고 [::-1]을 통해서 뒤집고 마지막으로 내가 애용하는 .join()을 사용한다면 리스트를 다시 문자열로 합쳐주는 아주 행복한 결과가 산출된다. 당연히 O(N)이기에 효율성도 좋다. C엔진 기반 파이썬 내장 함수의 장점이다.

---

class Solution:
    def reverseWords(self, s: str) -> str:
        # 1. s.split()으로 연속된 공백을 무시하고 단어만 리스트로 추출합니다.
        # 2. [::-1]을 사용해 리스트의 순서를 뒤집습니다.
        # 3. " ".join()을 사용해 단어들 사이에 공백 하나만 넣어서 합칩니다.
        
        return " ".join(s.split()[::-1])

---