투 포인터 알고리즘

두 개의 배열을 탐색하는 두 개의 포인터를 가지고 원하는 기능을 수행하게 하는 알고리즘

1차원 배열이 있고 이 배열에서 각자 다른 원소를 가리키고 있는 2개의 포인터를 조작해가면서 원하는 것을 얻는 형태이다. 이 때문에 투 포인터 알고리즘이라고 부른다.

두 배열 합치기

• 인풋 : 오름차순 정렬이 된 배열 두개
• 아웃풋 : 이 두개의 배열을 합쳐 오름차순 정렬된 상태로

function solution(arr1, arr2) {

  // high speed
  // sort n => nlogn
  // two pointer => O(n+m) => idea : 두 배열에 각각 chk를 두고 서로 비교하면서 작은 값을 푸시
  // 포인터가 두개라서 two pointer이다.
  const answer = [];
  let p1 = 0;
  let p2 = 0;

  while (true) {
    if (p1 === arr1.length || p2 === arr2.length) break;
    if (arr1[p1] > arr2[p2]) {
      answer.push(arr2[p2++]);
    } else {
      answer.push(arr1[p1++]);
    }
  }

  return arr1.length === p1
    ? answer.push(...arr2.slice(p2)) && answer
    : answer.push(...arr1.slice(p1)) && answer;
}

function solution(arr1, arr2) {
  // low speed
  return [...arr1, ...arr2].sort();

}

공통원소구하기

• 인풋 : 두 개의 정수 배열
• 아웃풋 : 공통된 원소만 들어가있는 배열

// high speed
function solution(arr1, arr2) {
  const answer = [];
  arr1 = arr1.sort((a,b)=>a>b);
  arr2 = arr2.sort((a,b)=>a>b);
  let p1 = 0;
  let p2 = 0;
  while (true) {
    if (p1 === arr1.length || p2 === arr2.length) break;
    if (arr1[p1] === arr2[p2]) {
      answer.push(arr1[p1]);
      p1++;
      p2++;
      continue;
    }
    if (arr1[p1] > arr2[p2]) {
      p2++;
      continue;
    }
    if (arr1[p1] < arr2[p2]) {
      p1++;
      continue;
    }
  }
  return answer;
}

//low speed
function solution(arr1, arr2) {
  return arr2.length > arr1.length
    ? arr2.filter((_) => arr1.includes(_))
    : arr1.filter((_) => arr2.includes(_));
}