[Toy] 6 - 10

6. sudoku

일부 칸이 비어있는(0이 입력된) 상태의 스도쿠 보드를 입력받아 완성된 보드를 리턴

  (board는 가로 길이와 세로 길이가 모두 9인 2차원 배열이다.)

const sudoku = function (board) {
  const N = board.length; // N = 9
  const boxes = [
    [0, 0, 0, 1, 1, 1, 2, 2, 2],
    [0, 0, 0, 1, 1, 1, 2, 2, 2],
    [0, 0, 0, 1, 1, 1, 2, 2, 2],
    [3, 3, 3, 4, 4, 4, 5, 5, 5],
    [3, 3, 3, 4, 4, 4, 5, 5, 5],
    [3, 3, 3, 4, 4, 4, 5, 5, 5],
    [6, 6, 6, 7, 7, 7, 8, 8, 8],
    [6, 6, 6, 7, 7, 7, 8, 8, 8],
    [6, 6, 6, 7, 7, 7, 8, 8, 8],
  ];
  const getBoxNum = (row, col) => boxes[row][col];

  const blanks = [];
  const rowUsed = [];
  const colUsed = [];
  const boxUsed = [];
  for (let row = 0; row < N; row++) {
    rowUsed.push(Array(N + 1).fill(false));
    colUsed.push(Array(N + 1).fill(false));
    boxUsed.push(Array(N + 1).fill(false));
  }

  for (let row = 0; row < N; row++) {
    for (let col = 0; col < N; col++) {
      if (board[row][col] === 0) {
        blanks.push([row, col]);
      } else {
        const num = board[row][col];
        const box = getBoxNum(row, col);
        rowUsed[row][num] = true;
        colUsed[col][num] = true;
        boxUsed[box][num] = true;
      }
    }
  }

  const isValid = (row, col, num) => {
    const box = getBoxNum(row, col);
    return (
      rowUsed[row][num] === false &&
      colUsed[col][num] === false &&
      boxUsed[box][num] === false
    );
  };

  const toggleNum = (row, col, num) => {
    const box = getBoxNum(row, col);
    board[row][col] = num;
    rowUsed[row][num] = !rowUsed[row][num];
    colUsed[col][num] = !colUsed[col][num];
    boxUsed[box][num] = !boxUsed[box][num];
  };

  const aux = (idx, blanks, board) => {
    if (idx === blanks.length) {
      return true;
    }

    const [row, col] = blanks[idx];
    for (let num = 1; num <= 9; num++) {
      if (isValid(row, col, num) === true) {
        toggleNum(row, col, num);
        if (aux(idx + 1, blanks, board) === true) {
          return true;
        }
        toggleNum(row, col, num);
      }
    }
    return false;
  };

  aux(0, blanks, board);
  return board;
};

---

7. treeDFS

임의의 tree를 구성하는 노드 중 하나의 Node 객체를 입력받아, 해당 노드를 시작으로 깊이 우선 탐색(DFS, Depth First Search)을 하여 탐색되는 순서대로 노드의 값이 저장된 배열을 리턴

let dfs = function (node) {
  let values = [node.value];

  node.children.forEach((n) => {
    values = values.concat(dfs(n)); // 재귀 이용
  });

  return values;
};

// 이 아래 코드는 변경 X
let Node = function (value) {
  this.value = value;
  this.children = [];
};

// 위 Node 객체로 구성되는 트리는 매우 단순한 형태의 트리이다.
// membership check(중복 확인)를 따로 하지 않는다.
Node.prototype.addChild = function (child) {
  this.children.push(child);
  return child;
};

---

8. largestProductOfThree

정수를 요소로 갖는 배열을 입력받아 3개의 요소를 곱해 나올 수 있는 최대값을 리턴

(단, 배열은 1차원 배열이며 음수와 0을 포함하고, 배열의 길이는 3 이상이다.)

const largestProductOfThree = function (arr) {
  const sorted = arr.slice().sort((a, b) => a - b);
  const len = arr.length;
  const case1 = sorted[len - 1] * sorted[len - 2] * sorted[len - 3];
  const case2 = sorted[len - 1] * sorted[0] * sorted[1];
  return Math.max(case1, case2);
};

---

9. power => 디버깅☆

두 수를 입력받아 거듭제곱을 리턴 (단, Math.pow와 거듭제곱 연산자를 사용하지 않는다.)

=> 실제 계산 결과를 94,906,249로 나눈 나머지를 리턴해야 한다. 계산 결과가 컴퓨터로 나타낼 수 있는 범위를 넘을 수 있기 때문에 나머지를 구해야 한다. 이때, 연산 중간에도 이 범위를 넘을 수 있으므로 모든 연산이 끝난 결과에서 나머지를 구하는 것이 아니라 연산할 때마다 나머지를 구하고 연산을 이어가야 한다.

function power(base, exponent) {
  if (exponent === 0) return 1;

  const half = parseInt(exponent / 2);
  const temp = power(base, half);
  const result = (temp * temp) % 94906249;

  if (exponent % 2 === 1) {
    return (base * result) % 94906249;
  } else {
    return result;
  }
}

---

10. binarySearch => 이진탐색 (O(logN))

오름차순 정렬된 정수의 배열(arr)과 정수(target)를 입력받아 target의 인덱스를 리턴 (단, target이 없으면 -1을 리턴)

const binarySearch = function (arr, target) {
  let start = 0;
  let end = arr.length - 1;
  
  while (start <= end) {
    let mid = parseInt((start + end) / 2);
    if (arr[mid] === target) {
      return mid;
    } else if (arr[mid] < target) {
      start = mid + 1;
    } else {
      end = mid - 1;
    }
  } return -1;
}