3sum

solution

값이 크다면, k의 값을 줄여야한다. 소팅되어있는 상황에서 값은 왼쪽으로 갈수록 작다. 따라서 작은 값을 더해야 값이 줄어들 수 있으므로(유망해질 수 있으므로) k의 값을 줄인다.

값이 작다면, j의 값을 키워야한다. 소팅되어있는 상황에서 값은 오른쪽으로 갈수록 커진다. 따라서 큰 값을 더해야 값이 커질 수 있으므로(유망해질 수 있으므로) j의 값을 키운다.

값이 같다면, j의 값을 키우고 k의 값을 줄여야한다. 초기화하는 느낌인데, 둘 중 하나의 작업만 수행하게되면, 절대 유망해질 수 없다. (k값을 줄여 값을 줄인다 하더라도, 이미 더한 값이 같은 상황에서 값이 줄어드는 것이라 절대 유망해질 수 없다. 마찬가지로, j의 값을 키워 값을 키운다 하더라도, 이미 더한 값이 같은 상황에서 값이 커지는 것이라 절대 유망해질 수 없다.)

 
    while(i !== nums.length-2){
        if(nums[i] > 0 ){
            break;
        }
        let j=i+1;
        let k=nums.length-1;
        
        while( j < k ){
            if(nums[j] + nums[k] < -1 * nums[i] ){
                j++;
            }else{
                if(nums[j] + nums[k] === -1 * nums[i]){
                    answer[`${nums[i]}${nums[j]},${nums[k]}`] = [nums[i],nums[j],nums[k]];
                    j++;
                    k--;
                    
                }else{
                    k--;
                    
                }
            }
            
        }
        i++;
        

    }    

Wrong case

내 방식은 값이 같거나 크게 되어버리면, i와 k값을 초기화시켰다. (나는 i와 k모두 오른쪽으로 증가하는 포인터였다. 그렇기 때문에 비교할 필요가 없는 유망하지 않은 경우도 계산에 포함되게 됨, 비효율적이다.)

   while(i !== nums.length-2){
        if(nums[i] > 0 ){
            break;
        }
        let j=i+1;
        let k=j+1;
        
        while(j !== nums.length - 1 ){
          
          
            if(nums[j] + nums[k] < -1 * nums[i] ){
                k++;
            }else{
                if(nums[j] + nums[k] === -1 * nums[i]){
                    answer[`${nums[i]}${nums[j]},${nums[k]}`] = [nums[i],nums[j],nums[k]];
                  
                    j = j+1;
                    k = j+1;
                    
                }else{
                    j = j+1;
                    k = j+1;
                    
                }
            }
            
        }
        i++;
   }

비교

앞에서 두 개의 포인터를 진행시키는 것은 덜 유망해도 검사하겠다는 의미. 비효율적이게됨

앞에 하나의 포인터, 뒤에 하나의 포인터를 두고 진행하게되면 유망한 것을 우선적으로 확인할 수 있게된다.

다음은 같은 경우의 횟수 비교이다.

배운점

하나를 고정시켰다면 두개의 포인터를 양끝에 배치시켜 계산해보는 발상해보자

다익스트라

링크