[JS] 재귀 with 백준

❗️ 병합정렬 - 백준 24060번

https://www.acmicpc.net/problem/24060

✅ mergesort 구현

function mergeSort(array) {
  if (array.length < 2) {
    return array;
  }
  let pivot = Math.floor(array.length / 2);
  let left = array.slice(0, pivot);
  let right = array.slice(pivot);
  return merge(mergeSort(left), mergeSort(right));
}
function merge(left, right) {
  let result = [];
  while (left.length && right.length) {
    if (left[0] <= right[0]) {
      result.push(left.shift());
    } else {
      result.push(right.shift());
    }
  }
  while (left.length) {
    result.push(left.shift());
  }
  while (right.length) {
    result.push(right.shift());
  }

  return result;
}
let arr = [4, 5, 1, 3, 2];
let answer = mergeSort(arr);
console.log(answer); // [1,2,3,4,5]

❗️ 칸토어 집합 - 백준 4779번

https://www.acmicpc.net/problem/4779

✅ merge & Kantoa 구현

const lists = [0, 1, 3, 2];

lists.forEach((N) => {
  let len = Math.pow(3, N);
  let string = "";
  for (let i = 0; i < len; i++) {
    string += "-";
  }
  console.log(Kantoa(string));
});

function Kantoa(arr) {
  if (arr.length < 2) {
    return arr;
  }
  let pivot = Math.floor(arr.length / 3);
  let first = arr.slice(0, pivot);
  let second = arr.slice(pivot, pivot * 2);
  let third = arr.slice(pivot * 2, pivot * 3);
  return merge(Kantoa(first), Kantoa(second), Kantoa(third));
}

function merge(first, second, third) {
  let string = "";
  let blank = "";
  string += first;
  for (let i = 0; i < second.length; i++) {
    blank += " ";
  }
  string += blank;
  string += third;

  return string;
}

❗️ 하노이 탑 - 백준 11729번

https://www.acmicpc.net/problem/11729

✅ hanoi 구현

const N = 3;
let count = 0;
function hanoi(number, from, to, other) {
  if (number === 0) {
    return;
  } else {
    hanoi(number - 1, from, other, to);
    console.log(`${from}에서 ${to}로 이동`);
    count++;
    hanoi(number - 1, other, to, from);
  }
}

hanoi(N, 1, 3, 2);
console.log(`${count}번 시행`);