210618 TIL

오늘 한 것

완전탐색 알고리즘

투포인트 알고리즘
2개의 배열을 비교하여, 어떠한 결과를 산출 할 때 2중 for문이 아니라 2개의 point를 구성해서 문제를 해결한다. 보통 while과 같이 사용하는 것 같다. 얻고자 하는 결과가 true 또는 false 에 따라 포인트를 움직여 2개의 값의 싱크를 조절한다.

문제 1

// 2개의 배열을 합치고, 오름차순으로 정렬

const solution = (list1, list2) => {
  let answer = [];
  let n = list1.length;
  let m = list2.length;
  let [p1, p2] = [0, 0];
  while (p1 < n && p2 < m) {
    if (list1[p1] <= list2[p2]) answer.push(list1[p1++]);
    else answer.push(list2[p2++]);
  }
  while (p1 < n) answer.push(list1[p1++]);
  while (p2 < m) answer.push(list2[p2++]);
  console.log(answer);
};

let arr1 = [1, 3, 5];
let arr2 = [2, 3, 6, 7, 9];
solution(arr1, arr2);

문제 2

// 배열 a와 b의 공통 원소를 추출하여 오름차순으로 출력

const solution = (arr1, arr2) => {
  let answer = [];
  let n = arr1.length;
  let m = arr2.length;
  let [p1, p2] = [0, 0];

  arr1.sort((a, b) => a - b);
  arr2.sort((a, b) => a - b);
  
  while (p1 < n && p2 < m) {
    if (arr1[p1] === arr2[p2]) {
      answer.push(arr1[p1]);
      p1++;
      p2++;
    } else if (arr1[p1] < arr2[p2]) p1++;
    else p2++;
  }

  console.log(answer);
};

let a = [1, 3, 9, 5, 2];
let b = [3, 2, 5, 7, 8];
solution(a, b);