알고리즘 -2021/03/30

문제

임의의 arr를 받아서 요소들의 합 중에 k와 동일한 것이 있다면 true를 반환하고 그렇지 않다면 false를 반환한다.

출력

arr k answer
[1,4,8] 12  true
[1,3,5] 12 false

풀이

// O(n^2)
function twoSum(arr, k) {
  let fix = 0;
  const len = arr.length;
  let newArr = [];
  while(fix < len-1){
    let firstNum = arr[fix];

     for(let i = fix +1; i < len; i++){
        newArr.push(firstNum + arr[i]);
     }
    fix +=1;
  }
  
  let result = newArr.includes(k);
  return result;
}

// array.sort O(n lg n) + 탐색 O(n) 또는 O(n lg n)
// 
function twoSum2(arr,k){
  const sortArr = arr.sort();
  let prefix = 0;
  let suffix = arr.length-1;
  const len = arr.length;
  
  //while은 false가 되야 멈춤
  while(prefix < suffix){
    //같지 않은 경우 오름차순이므로 suffix만 감소한다면 
    if(sortArr[prefix] + sortArr[suffix] === k){
      return true
    }else{
      if(sortArr[prefix] + sortArr[suffix] > k){
          suffix -=1;  
      } else {
        prefix += 1;
      }
    }
  }
  return false;
}  

// O(n), 공간 복잡도 O(n)

const test = twoSum([1,3,7], 10);
console.log(test);

const test2 = twoSum2([1,3,7], 10);
console.log(test2);

일단 기본적으로 for문을 두번 돌며 시간복잡도 n^2에 해당하는 답안이 가장 먼저 떠올라 작성을 하였다.

이 방법 같은 경우 모든 경우의 수를 생각하며 확인할 수 있다는 장점이 있으나 효율성에 대한 의문이 생기는 방법이 된다.

그래서 면접관님이 제시해주신 팁을 토대로 문제를 푸는것이 진행되었다.

이진탐색과 유사한 방식으로 진행되었다.

받은 k와 동일한지, k보다 합이 큰지, 작은지 에 대해서 판단을 하며 경우에 따라 prefix 와 suffix를 증가시켜 함수가 지속되고 prefix가 suffix를 넘어서는 경우 반복문이 종료되고
반복문이 종료될 때 까지 값을 찾지 못한다면 false가 반환되는 형태이다.

• ps. 알고리즘은 하면 할 수록 재미가 있는데 왜 계속 이중반복문 부터 생각나는지 모르겠다.
• ps2. 그리고 흥분하지 말자 제발 :) ...

참고

• 코딩테스트 했던 문제