코테 스터디 46일차 TIL + 오늘의 학습 키워드 two pointer

- 오늘의 학습 키워드

two pointer
- 공부한 내용 본인의 언어로 정리하기

 

투포인터를 사용하기 위해 배열을 정렬해야한다.

고정 + 투 포인터: 첫번째 원소를 고정하고 나머지 두 원소를 투포인터로 찾는다.

중복 제거 전략

two pointer 이동 규칙

-sum<0 더 큰값이 필요하므로 left++

-sum>0 더 작은 값이 필요하므로 right--

-sum==0 답을 찾았으므로 양쪽 포인터 모두 이동 

 

수도 코드

ALGORITHM ThreeSum(nums):
    result = []
    SORT(nums)
    
    FOR i = 0 to nums.length - 3:
        IF i > 0 AND nums[i] == nums[i-1]:
            CONTINUE  // 중복 건너뛰기
        
        left = i + 1
        right = nums.length - 1
        
        WHILE left < right:
            sum = nums[i] + nums[left] + nums[right]
            
            IF sum == 0:
                result.ADD([nums[i], nums[left], nums[right]])
                // 중복 건너뛰기
                WHILE left < right AND nums[left] == nums[left+1]:
                    left++
                WHILE left < right AND nums[right] == nums[right-1]:
                    right--
                left++
                right--
            ELSE IF sum < 0:
                left++
            ELSE:
                right--
    
    RETURN result

- 오늘의 회고
  - 어떤 문제가 있었고, 나는 어떤 시도를 했는지
  - 어떻게 해결했는지
  - 무엇을 새롭게 알았는지
  - 내일 학습할 것은 무엇인지

Valid Palindrome

Two Sum II Input Array Is Sorted

Container With Most Water

Trapping Rain Water