[21/08/16 KATA NINJA] leetcode #1

/**
 * @param {number[]} nums
 * @param {number} target
 * @return {number[]}
 */
var twoSum = function(nums, target) {
    for(let check=0;check<nums.length;check++){
        const first = nums[check]
        for(let check1=check+1;check1<nums.length;check1++){
            const second = nums[check1]
            
            if(first+second===target) return [check,check1] 
        }
    }
};

/**
 * @param {number[]} nums
 * @return {number[][]}
 */
var threeSum = function(nums) {
    let answer = []
    const numsIdx = nums.map((i,idx)=>idx)
    function DFS(array,r){
        if(r === 1){            
            return array.map(i=>[i]);
        }
        let result = []
        array.forEach((i,idx) => {            
            const dfs = DFS(array.slice(idx+1),r-1);
            const s = dfs.map(a => [i,...a]);
            result.push(...s);            
        })
        return result;
        
    }
    
   
    
    const combination = DFS(numsIdx,3);
    combination.forEach(i=>{
        let result = 0;
        let array = []
        i.forEach(a=>{
            result += nums[a];
            array.push(nums[a]);
        })
        if(result === 0){
            array = array.sort((a,b)=>a-b);
            answer[`${array[0]}${array[1]}${array[2]}`] = array;
        }
    })
    
    return Object.keys(answer).map(key=>answer[key]);

};

위와 같이 풀면 답은 맞아도 시간초과가 나게된다.

이 문제는 투포인터 알고리즘으로 풀어야한다.

투포인터 복습

말 그대로 두개의 포인터를 가지고 푸는 방법 => 시간을 충분히 단축 시킬 수 있다.

두 배열 정렬하여 합치기

[1,5,6]

[2,8]

이 인자로 주어지면 => [1,2,5,6,8] 로 만드는 문제.

아래와 같이 풀면 안됨. sort 자체의 복잡도가 O(nlogn)이다.

 function solution(arr1, arr2) {
     return [...arr1, ...arr2].sort();
 }

아래와 같이 풀면

O(n+m)으로 끝낼 수 있다.

function solution(arr1, arr2) {
  let answer = [];
  let p1 = 0;
  let p2 = 0;
  while (p1 !== arr1.length && p2 !== arr2.length) {
    answer.push(arr1[p1] > arr2[p2] ? arr2[p2++] : arr1[p1++]);
  }
  return p1 === arr1.length
    ? [...answer, ...arr2.slice(p2)]
    : [...answer, ...arr1.slice(p1)];
}

공통원소 구하기

[1,2,3,4,5]

[3,4,5,6,7]

이 주어지면 => 3,4,5를 골라내면 댐

다음과 같이 풀면 BABO다.. filter도 모든 원소를 순회하고 includes도 모든 원소를 순회하기 때문에 O(n^2)이 되어버림.

  return arr2.length > arr1.length
    ? arr2.filter((_) => arr1.includes(_))
    : arr1.filter((_) => arr2.includes(_));

투포인터로 풀면 다음과 같다.

function solution(arr1, arr2) { 
  let answer = [];
  let p1 = 0;
  let p2 = 0;

  // 우선 소팅을 해준다.
  arr1.sort((_, __) => _ - __);
  arr2.sort((_, __) => _ - __);

  
  
  // 양쪽을 순회하면서 작은 쪽의 값을 올려준다.
  
  
  // 소팅이 되어있으므로, 작은 값을 올리게 되면 큰 값과 비교했을 때 같은 값이 나올 수 있다.
  
  
  // 큰 값을 올리게되면, 죽어도 같은 값은 나올 수 없다. (순회 끝까지 가더라도)
  while (p1 !== arr1.length && p2 !== arr2.length) {
    if (arr1[p1] === arr2[p2]) {
      answer.push(arr1[p1]);
      p2++;
      p1++;
    } else {
      arr1[p1] > arr2[p2] ? p2++ : p1++;
    }
  }
  console.log(answer);
}

부분수열의 합

[1,2,1,3,1,1,1,2]과 6이 주어지면,

다음과 같이 투포인터로 풀 수 있다.

let p1 = 0;
  let p2 = 0;
  let answer = [];
  while (p1 !== arr.length && p2 !== arr.length) {
    const result = arr.slice(p1, p2 + 1).reduce((a, b) => a + b);
    if (result > m) {
      // 모두 더한 값이 크면, 왼쪽포인터 값을 올려야 한다. 크기 때문에 더 값을 더해봤자 의미 없다.
      p1++;
    } else {
      if (result === m) {
        
        // 모두 더한 값이 같다면, 왼쪽 포인터 값을 올린다. 마찬가지로 값을 더해봤자 m은 나올 수 없다.(양수만 있다고 가정하면)
        answer.push(arr.slice(p1, p2 + 1));
        p1++;
      } else {
        
        // 값이 더 작다면, 오른쪽 포인터 값을 올린다. 오른쪽 값을 올리게되면 m이 나올 수 있다.
        p2++;
      }
    }
  }

부분수열의 합이 특정 값 이하

말그대로 특정 값 이하가 되는 부분수열의 갯수를 구하면 된다.

function solution(arr, m) {
  // 갯수를 구하는 것이기 때문에 야매로
  let p1 = 0;
  let p2 = 0;
  let answer = 0;
  while (p1 !== arr.length && p2 !== arr.length) {
    const result = arr.slice(p1, p2 + 1).reduce((a, b) => a + b);
    if (result <= m) {
      answer += p2 - p1 + 1;
      p2++;
    } else {
      p1++;
    }
  }
  return answer;
}
console.log(solution([1, 3, 1, 2, 3], 5));