function star(n, mat, x, y) {
  if (n === 1) {
    mat[y][x] = "*";
    return;
  }

  let size = Math.floor(n / 3);
  for (let i = 0; i < 3; i++) {
    for (let j = 0; j < 3; j++) {
      if (i == 1 && j == 1) continue;
      star(size, mat, x + j * size, y + i * size);
    }
  }
}

function solution(n) {
  let mat = new Array(n).fill(0).map(() => new Array(n).fill(" "));

  star(n, mat, 0, 0);

  for (let i = 0; i < n; i++) {
    console.log(mat[i].join(""));
  }
}

solution(3);
solution(9);
solution(27);
// ***************************
// * ** ** ** ** ** ** ** ** *
// ***************************
// ***   ******   ******   ***
// * *   * ** *   * ** *   * *
// ***   ******   ******   ***
// ***************************
// * ** ** ** ** ** ** ** ** *
// ***************************
// *********         *********
// * ** ** *         * ** ** *
// *********         *********
// ***   ***         ***   ***
// * *   * *         * *   * *
// ***   ***         ***   ***
// *********         *********
// * ** ** *         * ** ** *
// *********         *********
// ***************************
// * ** ** ** ** ** ** ** ** *
// ***************************
// ***   ******   ******   ***
// * *   * ** *   * ** *   * *
// ***   ******   ******   ***
// ***************************
// * ** ** ** ** ** ** ** ** *
// ***************************

function solution(n, times) {
  let high = n * Math.max.apply(null, times);
  let low = 0;
  let mid, pass;

  while (low <= high) {
    mid = Math.floor((low + high) / 2);
    pass = times.reduce((sum, time) => (sum += Math.floor(mid / time)), 0);

    if (n <= pass) high = mid - 1;
    else low = mid + 1;
  }

  return low;
}

function solution(number, k) {
  let stack = [];

  for (let i = 0; i < number.length; i++) {
    while (stack.length !== 0 && stack[stack.length - 1] < number[i]) {
      stack.pop();

      if (--k === 0) {
        return stack.join("") + number.substr(i, number.length - i);
      }

    }
    stack.push(number[i]);
  }
  return stack.join("").substr(0, stack.length - k);
}

function isPossible(arr, row, col) {
  for (let c = 0; c < col; c++) {
    if (arr[c] == row) return false;
    if (Math.abs(c - col) === Math.abs(arr[c] - row)) return false;
  }
  return true
}

function dfs(n, arr, col) {
  if (col == n) return 1;

  let ret = 0;
  for (let row = 0; row < n; row++) {
    if (isPossible(arr, row, col)) {
      arr[col] = row;
      ret += dfs(n, arr, col + 1);
    }
  }
  return ret;
}

function solution(n) {
  return dfs(n, [], 0);
}

function dac(answer, arr, n, x, y) {
  let count = [0, 0];
  for (let j = y; j < y + n; j++) {
    for (let i = x; i < x + n; i++) {
      count[arr[j][i]]++;
    }
  }

  if (count[0] === 0) {
    answer[1]++;
    return;
  }

  if (count[1] === 0) {
    answer[0]++;
    return;
  }

  dac(answer, arr, Math.floor(n / 2), x, y);
  dac(answer, arr, Math.floor(n / 2), Math.floor(x + n / 2), y);
  dac(answer, arr, Math.floor(n / 2), x, Math.floor(y + n / 2));
  dac(
    answer,
    arr,
    Math.floor(n / 2),
    Math.floor(x + n / 2),
    Math.floor(y + n / 2)
  );
}

function solution(arr) {
  let answer = [0, 0];
  dac(answer, arr, arr.length, 0, 0);
  return answer;
}

function solution(citations) {
  var answer = 0;
  citations.sort((x, y) => y - x);
  for (let i = 0; i < citations.length; i++) {
    if (citations[i] >= i + 1) answer = i + 1;
  }
  return answer;
}

function Truck(weight, time) {
  this.weight = weight;
  this.time = time;
}

function solution(bridge_length, weight, truck_weights) {
  let queue = [];
  let head = 0;
  let tail = 0;

  let truck_index = 0;
  let total_weight = 0;
  let time = 0;

  queue[tail++] = new Truck(truck_weights[truck_index], bridge_length + time);
  total_weight += truck_weights[truck_index++];
  time++

  while (head != tail) {
    // 1. 다리에 올라간 트럭이 다리 길이보다 작아야 한다.
    // 2. 다리에 올라간 트럭들 무게와 다음 올라갈 트럭의 무게의 합이 weight보다 작거나 같아야 한다.
    // 3. 시간이 지나면서 트럭이 빠지거나, 다 빠질때까지 대기해야한다

    // 다리를 지난 트럭 처리
    if (queue[head].time === time) {
      total_weight -= queue[head++].weight;
    }

    if (
      tail - head < bridge_length &&
      total_weight + truck_weights[truck_index] <= weight
    ) {
      queue[tail++] = new Truck(
        truck_weights[truck_index],
        bridge_length + time
      );
      total_weight += truck_weights[truck_index++];
    } else if (queue[head]) {
      time = queue[head].time - 1;
    }
    time++;
  }
  return time;
}

function Graph() {
  this.edge = {};
  this.visited = {};
}

Graph.prototype.addVertex = function (v) {
  this.edge[v] = [];
  this.visited[v] = 0;
};

Graph.prototype.addEdge = function (v1, v2) {
  this.edge[v1].push(v2);
  this.edge[v2].push(v1);
};

function solution(n, edge) {
  // 1. graph 객체 > edge로 자료구조화
  let g = new Graph();
  for (let i = 1; i <= n; i++) {
    g.addVertex(i);
  }
  for (let i = 0; i < edge.length; i++) {
    g.addEdge(edge[i][0], edge[i][1]);
  }
  // 2. bfs 구현 및 수행 > 노드 별 최단 경로가 얼마인지 산출 (queue)
  // 3. 가장 먼 경로 확인 후 먼 경로의 값을 갖는 노드 개수를 확인하여 반환
  let queue = [];
  let head = 0,
    tail = 0,
    max = 0;
  queue[tail++] = [1, 1];
  g.visited[1] = 0;

  while (head != tail) {
    let [n, c] = queue[head++];

    if (g.visited[n]) continue;

    g.visited[n] = c;
    if (c > max) max = c;

    for (let i = 0; i < g.edge[n].length; i++) {
      if (!g.visited[g.edge[n][i]]) {
        queue[tail++] = [g.edge[n][i], c + 1];
      }
    }
  }

  return Object.values(g.visited).reduce(
    (pre, val) => pre + (val === max ? 1 : 0),
    0
  );
}