코테 스터디 35일차 TIL + 오늘의 학습 키워드 투포인터 brute force 말고 투포인터

- 오늘의 학습 키워드 정렬 + 투포인터
- 공부한 내용 본인의 언어로 정리하기

1. 배열을 먼저 정렬한다

2. 고정값을 선택: 첫번째 원소를 고정한다

3. two pointer로 나머지 두 원소를 투포인터로 찾는다

middle = left+1

right = nums.length -1

 

수도코드

1.  배열을 오름차순으로 정렬
for( i =0 to nums.length -3)
  a. 중복제거
  b. middle = i+1; right = nums.length-1
  c. while middle <right;
    sum = nums[i]+ nums[middle] + nums[right]
    if sum==0: 결과에 추가, 중복제거하고 포인터를 이동
    	else if sum <0 : middle ++
        else : right--

 

 

 

- 오늘의 회고
  - 어떤 문제가 있었고, 나는 어떤 시도를 했는지

// ❌ 일반적인 이중 순회 (Brute Force)
for (int left = i + 1; left < nums.length - 1; left++) {
    for (int right = left + 1; right < nums.length; right++) {
        // 모든 조합을 다 확인 O(n²)
    }
}

이전날 문제에 투포인터 문제가 나와서 right 가 0부터 +1씩 순회하는것으로 문제를 풀려고 시도했으나 

그런 방식으로 접근을 하니까 left를 증가시키는 것이 불가하고 middle 값을 어떻게 정해야할지 감이 안옴

중복제거를 이렇게 간단하게 할수 있는지 몰랐음 continue라니 

  - 어떻게 해결했는지
  - 무엇을 새롭게 알았는지

 

투포인터 방식

int left =i+1;
int right = nums.length -1;
while(left <right){
    if(sum<0) left ++;
    else if(sum>0) right--;
    else {//찾은 경우
    
    left ++; right--;
    }

}

 

  - 내일 학습할 것은 무엇인지