두시간 알고리즘 - 5일차, two pointer(2)

https://leetcode.com/tag/two-pointers/

더 풀어야징

 

 

1.  3Sum: 29m02s95

https://leetcode.com/problems/3sum/

/**
 * @param {number[]} nums
 * @return {number[][]}
 */
var threeSum = function(nums) {
    nums.sort((a, b) => a - b);
    
    const answer = [];
    
    const checker = new Set();
    for(let k = 0; k < nums.length - 2; k++){
        if(checker.has(nums[k])){
            continue;
        }
        
        checker.add(nums[k]);
        const target = 0 - nums[k];
        
        let left = k+1;
        let right = nums.length - 1;
        
        while(left < right){
            const leftValue = nums[left];
            const rightValue = nums[right];
            const sum = leftValue + rightValue;
            
            if(target < sum){
                right--;
            }else if(target > sum){
                left++;
            }else{
                answer.push([nums[k], nums[left], nums[right]]);
                while(left < right){
                    left++;
                    if(leftValue !== nums[left]){
                        break;
                    }
                }
                while(left < right){
                    right--;
                    if(rightValue !== nums[right]){
                        break;
                    }
                }
            } 
        }
    }
    
    return answer;
};

 

속도가 좀 이상하게 나온다. 같은코드 여러번 돌려도 다른 속도. 

 

 

 

 

2. Remove Nth Node From End of List: 56m06s45

https://leetcode.com/problems/remove-nth-node-from-end-of-list/

이문제는 생각을 정리하는데 애를 먹었다. 

/**
 * Definition for singly-linked list.
 * function ListNode(val, next) {
 *     this.val = (val===undefined ? 0 : val)
 *     this.next = (next===undefined ? null : next)
 * }
 */
/**
 * @param {ListNode} head
 * @param {number} n
 * @return {ListNode}
 */
var removeNthFromEnd = function(head, n) {
    if(head.next === null){
        return null
    }
    
    let last = head;
    for(let i = 0; i < n-1; i++){
        last = last.next;
    }
  
    if(!last.next){
        // 이미 마지막 원소, 첫번째꺼를 지워주면된다
        return head.next;
    }
    
    last = last.next;
    prev = head;
    cur = head.next;
    
    while(last.next){
        last = last.next;
        prev = prev.next;
        cur = cur.next;
    }
    
    prev.next = cur.next;
    
    return head
};

마지막거를 가리키는거랑, 거기서부터 n번째 원소와, 그 하나 앞까지를 계속 포인터로 가리키고 있다가 마지막을 찾는 애가 진짜 마지막을 찾으면 거기서부터 n번째 원소인애를 지워줬다. 

 

- 좀 삽질을 한것 같아서 해설도 봐주었다. 

https://www.youtube.com/watch?v=XVuQxVej6y8 

정말...풀이는 간결하다~ 가장 앞부분에 노드를 처리하는게 어려웠는데, dummy node를 앞에 삽입해서 해결을 할 수 있다. 포인터도 세개나할것도 없고. 그냥 node.next.next하면 되는거였다...

 

3.  Rotate List: 26m41s47

https://leetcode.com/problems/rotate-list/

/**
 * Definition for singly-linked list.
 * function ListNode(val, next) {
 *     this.val = (val===undefined ? 0 : val)
 *     this.next = (next===undefined ? null : next)
 * }
 */
/**
 * @param {ListNode} head
 * @param {number} k
 * @return {ListNode}
 */
var rotateRight = function(head, k) {
    let dummy = new ListNode(-1, head);
    let len = 0;
    let cursor = dummy.next;
    
    while(cursor){
        len++;
        cursor = cursor.next
    }
    
    k %= len;
    
    if(k === 0){
        return head;
    }
    
    let left = dummy;
    let right = head;
    let prevRight = dummy;
    for(let i = 0; i < k; i++){
        prevRight = right;
        right = right.next;
    }
     
    while(right){
        left = left.next;
        right = right.next
        prevRight = prevRight.next;
    }
    
    // console.log(left, right, prevRight);
    
    dummy.next = left.next; // 새로 이어붙이고,
    left.next = null; // 기존거에서는 잘라냈다. 
    prevRight.next = head; // 마지막위치에는 head를 넣는다

    
    return dummy.next
    
};

풀긴했는데 영찜찜하다. 

 

 

후기

오늘은 뭔가 좀 다 찜찜하게 풀려서 썩 유쾌하지 않구만. 하지만 풀리긴한다. 포인터 두개가지고 왜 난리였던건지 조금은 이해가 된다.