1 ~ n의 번호가 있는 택배 상자가 창고에 있습니다. 당신은 택배 상자들을 다음과 같이 정리했습니다.

왼쪽에서 오른쪽으로 가면서 1번 상자부터 번호 순서대로 택배 상자를 한 개씩 놓습니다. 가로로 택배 상자를 w개 놓았다면 이번에는 오른쪽에서 왼쪽으로 가면서 그 위층에 택배 상자를 한 개씩 놓습니다. 그 층에 상자를 w개 놓아 가장 왼쪽으로 돌아왔다면 또다시 왼쪽에서 오른쪽으로 가면서 그 위층에 상자를 놓습니다. 이러한 방식으로 n개의 택배 상자를 모두 놓을 때까지 한 층에 w개씩 상자를 쌓습니다.

위 그림은 w = 6일 때 택배 상자 22개를 쌓은 예시입니다. 다음 날 손님은 자신의 택배를 찾으러 창고에 왔습니다. 당신은 손님이 자신의 택배 상자 번호를 말하면 해당 택배 상자를 꺼내줍니다. 택배 상자 A를 꺼내려면 먼저 A 위에 있는 다른 모든 상자를 꺼내야 A를 꺼낼 수 있습니다. 예를 들어, 위 그림에서 8번 상자를 꺼내려면 먼저 20번, 17번 상자를 꺼내야 합니다.

당신은 꺼내려는 상자 번호가 주어졌을 때, 꺼내려는 상자를 포함해 총 몇 개의 택배 상자를 꺼내야 하는지 알고 싶습니다.

창고에 있는 택배 상자의 개수를 나타내는 정수 n, 가로로 놓는 상자의 개수를 나타내는 정수 w와 꺼내려는 택배 상자의 번호를 나타내는 정수 num이 매개변수로 주어집니다. 이때, 꺼내야 하는 상자의 총개수를 return 하도록 solution 함수를 완성해 주세요.

풀이

• 만약 해당하는 숫자가 맨 위라면 (n - num <= w) 바로 뺄 수 있음 (return 1)
• 그게 아니라면 맨 마지막 숫자와 대상 숫자 층 계산
• 층 사이만큼은 무조건 가야하므로 그만큼 return값에 추가 (res = c1 - c2)
• 만약 각 층수의 기우성이 같다고, 꼭대기 층의 값이 더 크다면 +1
• 기우성이 다르고, 꼭대기 층 값과 대상값의 합이 w를 넘는다면 +1

function solution(n, w, num) {
  if (n - num <= w) return 1;

  let res = 0;

  const c1 = Math.ceil(n / w);
  const c2 = Math.ceil(num / w);

  let r1 = n % w;
  let r2 = num % w;

  res = c1 - c2;
  if (c1 % 2 === c2 % 2) {
    if (r1 >= r2) res++;
  } else {
    if (!r1) r1 = w;
    if (!r2) r2 = w;
    if (r1 + r2 >= w) res++; 
  }


  return res;
}

N행 M열의 2차원 격자 grid가 주어집니다. 격자의 각 칸은 한 변의 길이가 √2인 정사각형이며, 각 칸 안에는 대각선이 하나 그어져 있습니다. 이 대각선은 / 방향(1) 또는 \ 방향(-1) 중 하나입니다.

각 정사각형 칸은 대각선에 의해 동일한 크기의 직각삼각형 두 개로 나뉘며, 당신은 각 칸에서 두 삼각형 중 정확히 하나만 색칠할 수 있습니다. 색칠된 삼각형들은 한 '변'을 공유해야 서로 연결되며, 이렇게 연결된 삼각형들의 집합을 하나의 삼각형 덩어리라고 합니다.

당신의 목표는 격자 전체를 적절히 색칠하여, 연결된 하나의 삼각형 덩어리 중 가능한 가장 큰 덩어리의 넓이를 구하는 것입니다. 각 삼각형의 넓이는 칸을 이루는 정사각형의 면적(2)의 절반인 1입니다. 따라서 덩어리에 포함된 삼각형의 개수가 곧 그 덩어리의 넓이가 됩니다.

격자의 상태를 나타내는 2차원 정수 배열 grid가 매개변수로 주어집니다. 이 격자를 적절히 색칠했을 때, 만들 수 있는 삼각형 덩어리들 중에서 가장 넓이가 큰 덩어리의 넓이를 return 하도록 solution 함수를 완성해 주세요.

풀이

• 각 셀은 왼쪽, 오른쪽 기준으로 나눔
• 각 칸은 좌/상 or 우/하 로 갈 수 있는 연결 그래프 형태(탐색 가능)
• 일반적인 탐색처럼 x,y +-1로 가는 탐색이 아니므로, 다음 노드를 구하는 함수 구현
• 한번의 탐색으로 갈 수 있는 모든 칸을 구함
  • 해당 칸은 무조건 순환하거나 1자형 길이 됨
• 그러한 길들의 x, y 좌표를 수집 후 배열에 순서대로 저장
• 순서대로 저장된 길을 투포인터로 2개의 동일한 점을 지나지 않게 하는 최대 길이를 구함
• 만약 순환한다면, 돌 수 있으므로 배열 * 2 해줌 (단, 임계값 설정 후 넘지 않는지 체크 필요)

function solution(grid) {
  const n = grid.length;
  const m = grid[0].length;
  let visCount = -1;
  const visited = new Array(n)
    .fill()
    .map(() => new Array(m).fill().map(() => new Array(2).fill(-1)));

  function getNexts(i, j, k) {
    const nexts = [];
    const flag = grid[i][j];
    if (flag === 1) {
      if (k === 0) {
        if (j !== 0) nexts.push([i, j - 1, 1]);
        if (i !== 0) {
          const aFlag = grid[i - 1][j];
          if (aFlag === 1) nexts.push([i - 1, j, 1]);
          else nexts.push([i - 1, j, 0]);
        }
      } else {
        // k === 1
        if (j !== m - 1) nexts.push([i, j + 1, 0]);
        if (i !== n - 1) {
          const aFlag = grid[i + 1][j];
          if (aFlag === 1) nexts.push([i + 1, j, 0]);
          else nexts.push([i + 1, j, 1]);
        }
      }
    } else {
      // flag === -1
      if (k === 0) {
        if (j !== 0) nexts.push([i, j - 1, 1]);
        if (i !== n - 1) {
          const aFlag = grid[i + 1][j];
          if (aFlag === 1) nexts.push([i + 1, j, 0]);
          else nexts.push([i + 1, j, 1]);
        }
      } else {
        // k === 1
        if (j !== m - 1) nexts.push([i, j + 1, 0]);
        if (i !== 0) {
          const aFlag = grid[i - 1][j];
          if (aFlag === 1) nexts.push([i - 1, j, 1]);
          else nexts.push([i - 1, j, 0]);
        }
      }
    }
    return nexts;
  }

  function calculate(merged, isCycle) {
    if (!merged.length) return 0;
    let limit = merged.length;
    const dupCheckSet = new Set();
    let isDupExist = false;
    for (const el of merged) {
      if (dupCheckSet.has(el)) {
        isDupExist = true;
        break;
      }
      dupCheckSet.add(el);
    }
    if (isDupExist) limit--;

    let ret = 0;
    if (isCycle) {
      const dup = [...merged];
      for (const el of merged) dup.push(el);
      merged = dup;
    }
    let left = 0;
    const memo = new Map();
    let dupCounts = 0;
    const addMemo = el => {
      if (!memo.has(el)) {
        memo.set(el, 1);
        return;
      }
      const v = memo.get(el);
      if (v === 1) dupCounts++;
      memo.set(el, v + 1);
    };
    const checkCondition = () => {
      return dupCounts < 1;
    };
    const removeMemo = el => {
      const v = memo.get(el);
      if (v === 2) dupCounts--;
      if (v === 1) memo.delete(el);
      else memo.set(el, v - 1);
    };

    for (let right = 0; right < merged.length; right++) {
      addMemo(merged[right]);
      while (!checkCondition()) {
        removeMemo(merged[left]);
        left++;
      }
      ret = Math.max(ret, right - left + 1);
    }

    return Math.min(limit, ret);
  }

  function go(i, j, k) {
    const acc = [];
    if (visited[i][j][k] === visCount) return acc;
    const key = i * m + j;
    acc.push(key);
    let queue = [[i, j, k]];
    visited[i][j][k] = visCount;
    while (queue.length) {
      const newQueue = [];
      for (const [x, y, z] of queue) {
        const nexts = getNexts(x, y, z);
        for (const next of nexts) {
          const [nx, ny, nz] = next;
          if (visited[nx][ny][nz] !== visCount) {
            acc.push(nx * m + ny);
            newQueue.push(next);
            visited[nx][ny][nz] = visCount;
          }
        }

        queue = newQueue;
      }
    }
    return acc;
  }

  function check(i, j, k) {
    const nexts = getNexts(i, j, k);
    visited[i][j][k] = ++visCount;
    if (!nexts.length) return 1;
    const results = nexts.map(([x, y, z]) => {
      return go(x, y, z);
    });
    const isCycle = results.length === 2 && results[1].length === 0;
    const merged = results[0];
    merged.reverse();
    merged.push(i * m + j);
    if (results.length === 2) {
      for (const el of results[1]) {
        merged.push(el);
      }
    }

    return calculate(merged, isCycle);
  }

  let res = 0;

  for (let i = 0; i < n; i++) {
    for (let j = 0; j < m; j++) {
      for (let k = 0; k < 2; k++) {
        if (visited[i][j][k] === -1) {
          res = Math.max(res, check(i, j, k));
        }
      }
    }
  }

  return res;
}

세로 길이가 n, 가로 길이가 m인 직사각형 모양의 격자판이 있습니다. 가장 왼쪽 위 격자의 좌표는 (1, 1)이고, 가장 오른쪽 아래 격자의 좌표는 (n, m)입니다.

각 격자의 양면에는 자연수가 적혀있습니다. 초기 상태에서는 각 격자의 한 면만이 보이도록 놓여 있습니다.

당신은 아래의 행동을 원하는 만큼 수행할 수 있습니다. 행동을 한번 수행할 때마다 비용 k가 소모됩니다.

격자판의 하나의 행 혹은 하나의 열에 존재하는 모든 격자를 뒤집어 보이는 면과 숨겨진 면을 교체할 수 있습니다. 모든 행동을 마친 후, (1, 1) 격자에 위치한 말을 (n, m) 격자까지 이동하면서 방문한 격자들의 보이는 수를 점수에 더합니다. 말을 이동할 때는 상하좌우로 인접한 격자로만 이동할 수 있으며, 한번 방문한 격자는 다시 방문할 수 없습니다.

이때, 말을 이동시켜 얻을 수 있는 점수 총합 - 총 비용의 최댓값을 구하려고 합니다.

예를 들어, 아래 그림과 같이 n = 2, m = 2인 격자판이 있고, k = 0이라고 가정해 보겠습니다.

아래와 같이 첫 번째 행과 두 번째 행을 뒤집고 말을 (5 → 7 → 8)과 같이 이동시키면 점수 총합은 20이고 총 비용은 0이며, 이때가 점수 총합 - 총 비용이 최대입니다.

각 격자의 현재 보이는 면에 적힌 수를 나타낸 2차원 정수 배열 visible과, 숨겨진 면에 적힌 수를 나타낸 2차원 정수 배열 hidden이 매개변수로 주어집니다. 점수 총합 - 총 비용의 최댓값을 return 하도록 solution 함수를 완성해 주세요.

풀이

• 행, 열의 개수 둘 중 하나라도 홀수이면 모든 판 다 돌수 있음(각 VALUE가 양수이므로 도는게 이득)
• 짝수인경우, i + j가 짝수인칸 중 제일 작은칸 제외하면됨
• 세로줄 n 최대값이 14이고, 2^14 는 약 1~2만 이므로 다항시간안에 순회 가능
• 2^14 경우 모두 순회하면서 greedy하게 세로줄 뒤집는 경우 계산

function calculate(matrix, hidden, n, m, k, isAllEven) {
  const colSum = new Array(m).fill().map(() => new Array(2).fill(0));
  for (let i = 0; i < n; i++) {
    for (let j = 0; j < m; j++) {
      colSum[j][0] += matrix[i][j];
      colSum[j][1] += hidden[i][j];
    }
  }

  let res = 0;
  for (let i = 0; i < m; i++) {
    res += Math.max(colSum[i][0], colSum[i][1] - k);
  }

  if (isAllEven) {
    let min = Infinity;
    for (let i = 0; i < n; i++) {
      for (let j = 0; j < m; j++) {
        if ((i + j) % 2 === 0) continue;
        let val;
        if (colSum[j][0] === colSum[j][1] - k) {
          val = Math.min(matrix[i][j], hidden[i][j]);
        } else if (colSum[j][0] > colSum[j][1] - k) {
          val = matrix[i][j];
        } else {
          val = hidden[i][j];
        }

        min = Math.min(min, val);
      }
    }

    res -= min;
  }

  return res;
}

function solution(visible, hidden, k) {
  const n = visible.length; // 1 ~ 14
  const m = visible[0].length; // 2 ~ 100
  const isAllEven = n % 2 === 0 && m % 2 === 0;

  const cases = 1 << n;
  let res = 0;
  for (let i = 0; i < cases; i++) {
    let cost = 0;
    for (let j = 0; j < n; j++) {
      if (i & (1 << j)) {
        [visible[j], hidden[j]] = [hidden[j], visible[j]];
        cost += k;
      }
    }

    res = Math.max(res, calculate(visible, hidden, n, m, k, isAllEven) - cost);

    for (let j = 0; j < n; j++) {
      if (i & (1 << j)) {
        [visible[j], hidden[j]] = [hidden[j], visible[j]];
      }
    }
  }

  return res;
}

한밤중 큰 눈이 내려 공원에 눈이 쌓였습니다. 공원은 n × m 크기의 직사각형 격자로 나타낼 수 있습니다. 격자의 r행 c열의 좌표는 (r, c)로 표현합니다. 각 격자 칸은 [눈이 쌓인 칸 / 눈덩이가 있는 칸 / 벽] 셋 중 하나입니다. 격자에는 크기가 1인 눈덩이 두 개만 존재합니다.

당신은 격자에 있는 눈덩이를 상하좌우로 인접한 벽이 아닌 칸으로 원하는 만큼 굴릴 수 있습니다.

눈덩이를 A칸에서 B칸으로 굴리면 B칸의 상태에 따라 다음과 같은 일이 일어납니다.

눈이 쌓인 칸 : 눈덩이의 크기가 1 늘어나고, B칸에 쌓여 있던 눈은 사라집니다. 눈이 없는 칸 : 한 번 눈덩이를 굴린 적이 있는 칸에는 눈덩이를 굴려도 크기가 커지지 않습니다. 다른 눈덩이가 있는 칸 : A칸의 눈덩이는 머리가 되고 B칸의 눈덩이는 몸통이 되어 눈사람이 만들어집니다. 눈사람이 된 눈덩이는 더 이상 굴릴 수 없습니다. 단, 머리가 되는 눈덩이가 몸통이 되는 눈덩이보다 크면 눈사람이 만들어지지 않고 눈덩이가 무너져 사라집니다.

n = 4, m = 5인 격자의 예시입니다.

(2, 2)에 있는 눈덩이를 위로 한 칸 굴리면 크기가 1 늘어납니다. (1 → 2)

(3, 2)에 있는 눈덩이를 그림의 화살표대로 굴리면 크기가 3 늘어납니다. (1 → 4)

크기가 2인 눈덩이를 아래로 굴려 크기가 4인 눈덩이 위에 올리면 눈사람을 만들 수 있습니다. 한번 눈사람을 만들면 더 이상 눈덩이를 굴릴 수 없습니다. 눈덩이를 굴리는 방법에 따라 여러 가지 크기의 눈사람이 만들어질 수 있습니다. 당신은 만들 수 있는 눈사람의 종류가 얼마나 될지 알고 싶습니다. 눈사람의 머리 혹은 몸통의 크기가 하나라도 다르다면 서로 다른 종류의 눈사람으로 셉니다. (눈사람이 만들어진 위치가 달라도 머리, 몸통의 크기가 같다면 한 번만 셉니다.)

풀이

풀이 및 코드 재작성중...

/* eslint-disable prefer-const */
/* eslint-disable max-classes-per-file */
class QueueNode {
  constructor(value) {
    this.value = value;
    this.next = null;
  }
}

class Queue {
  constructor() {
    this.head = null;
    this.tail = null;
  }

  push(value) {
    const newNode = new QueueNode(value);
    if (!this.head) {
      this.head = newNode;
      this.tail = newNode;
      return;
    }
    this.tail.next = newNode;
    this.tail = this.tail.next;
  }

  pop() {
    const { value } = this.head;
    this.head = this.head.next;
    if (!this.head) {
      this.tail = null;
    }
    return value;
  }

  empty() {
    return !this.head;
  }
}

const dx = [0, 0, 1, -1];
const dy = [1, -1, 0, 0];

function isValidPos(x, y, n, m) {
  return x >= 0 && x < n && y >= 0 && y < m;
}

function countValidRoots(grid, n, m, cur, dest, visited) {
  if (!visited) {
    visited = new Array(n).fill().map(() => new Array(m).fill(false));
    visited[cur[0]][cur[1]] = true;
  }

  const queue = new Queue();
  queue.push(cur);
  let ret = 0;
  while (!queue.empty()) {
    const pos = queue.pop();
    if (ret > 1) return ret;
    for (let k = 0; k < 4; k++) {
      const mx = pos[0] + dx[k];
      const my = pos[1] + dy[k];
      if (
        isValidPos(mx, my, n, m) &&
        !visited[mx][my] &&
        grid[mx][my] !== '#'
      ) {
        if (mx === dest[0] && my === dest[1]) {
          ret++;
        } else {
          visited[mx][my] = true;
          queue.push([mx, my]);
        }
      }
    }
  }
  return ret;
}

function findStartEnd(n, m, grid) {
  let start = null;
  let end = null;

  for (let i = 0; i < n; i++) {
    for (let j = 0; j < m; j++) {
      if (grid[i][j] === 'o') {
        if (!start) {
          start = [i, j];
        } else {
          end = [i, j];
        }
      }
    }
  }
  return { start, end };
}

function getDist(n, m, grid, start, end) {
  const visited = new Array(n).fill().map(() => new Array(m).fill(false));
  const queue = new Queue();
  queue.push([start, 0]);
  visited[start[0]][start[1]] = true;
  while (!queue.empty()) {
    const [pos, dist] = queue.pop();
    if (pos[0] === end[0] && pos[1] === end[1]) {
      return dist - 1;
    }
    for (let k = 0; k < 4; k++) {
      const mx = pos[0] + dx[k];
      const my = pos[1] + dy[k];
      if (
        isValidPos(mx, my, n, m) &&
        !visited[mx][my] &&
        grid[mx][my] !== '#'
      ) {
        visited[mx][my] = true;
        queue.push([[mx, my], dist + 1]);
      }
    }
  }

  return -1;
}

function getSnowCounts(n, m, mergedMap) {
  const ret = {
    aTotal: 0,
    bTotal: 0,
    commonTotal: 0,
  };
  for (let i = 0; i < n; i++) {
    for (let j = 0; j < m; j++) {
      if (mergedMap[i][j] === 1 << 0) ret.aTotal++;
      if (mergedMap[i][j] === 1 << 1) ret.bTotal++;
      if (mergedMap[i][j] === ((1 << 0) | (1 << 1))) ret.commonTotal++;
    }
  }

  return ret;
}

function fillMergedMap(n, m, grid, start, mergedMap, flag) {
  const visited = new Array(n).fill().map(() => new Array(m).fill(false));
  const queue = new Queue();
  queue.push(start);
  visited[start[0]][start[1]] = true;
  mergedMap[start[0]][start[1]] |= flag;
  while (!queue.empty()) {
    const pos = queue.pop();
    for (let k = 0; k < 4; k++) {
      const mx = pos[0] + dx[k];
      const my = pos[1] + dy[k];
      if (
        isValidPos(mx, my, n, m) &&
        !visited[mx][my] &&
        grid[mx][my] !== '#'
      ) {
        visited[mx][my] = true;
        mergedMap[mx][my] |= flag;
        if (grid[mx][my] !== 'o') {
          queue.push([mx, my]);
        }
      }
    }
  }
}

function checkRotatable(n, m, mergedMap, flag, start) {
  const visited = new Array(n).fill().map(() => new Array(m).fill(false));
  const queue = new Queue();
  queue.push([start, 1]);
  visited[start[0]][start[1]] = true;
  let latestCount = 1;
  while (!queue.empty()) {
    const [pos, count] = queue.pop();
    latestCount = count;
    let valids = 0;
    for (let k = 0; k < 4; k++) {
      const mx = pos[0] + dx[k];
      const my = pos[1] + dy[k];
      if (!isValidPos(mx, my, n, m)) continue;
      if (mergedMap[mx][my] !== flag) continue;
      if (visited[mx][my]) continue;
      valids++;
      visited[mx][my] = true;
      queue.push([[mx, my], count + 1]);
    }
    if (valids >= 2) return [true, count];
  }

  return [false, latestCount - 1];
}

// common은 두 점 포함, A가 더 큰놈
function calculator(aLeft, aRight, bLeft, bRight, common, total) {
  let ret = 0;
  for (let b = bLeft; b <= bRight; b++) {
    const aMin = Math.max(aLeft, common - b, b);
    const aMax = Math.min(aRight, total - b);

    if (aMin <= aMax) {
      ret += aMax - aMin + 1;
    }
  }
  return ret;
}

function calculate(
  isARotateble,
  aLeast,
  aTotal,
  isBRotatable,
  bLeast,
  bTotal,
  // isCommonRotatable,
  commonLeast,
  commonTotal,
  validRootCounts,
) {
  const totalSnowCounts = commonTotal + aTotal + bTotal;
  // if (isCommonRotatable) {
  //   if (validRootCounts === 1) {
  //     // eslint-disable-next-line no-unused-vars
  //     const [minTotal, maxTotal] =
  //       aTotal > bTotal ? [bTotal, aTotal] : [aTotal, bTotal];

  //     return calculator(
  //       1,
  //       totalSnowCounts - 1,
  //       1,
  //       maxTotal + commonTotal - 1,
  //       commonLeast,
  //       totalSnowCounts,
  //     );
  //   }

  //   return calculator(
  //     1,
  //     totalSnowCounts - 1,
  //     1,
  //     totalSnowCounts - 1,
  //     commonLeast,
  //     totalSnowCounts,
  //   );
  // }


  if (!isARotateble) {
    const [min, max] = aTotal < bTotal ? [aTotal, bTotal] : [bTotal, aTotal];
    return calculator(
      1,
      max + commonTotal - 1,
      1,
      min + commonTotal - 1,
      commonLeast,
      totalSnowCounts,
    );
  }

  // A에서 돌릴수 있음 ㅇㅇ
  // 무조건 A가 크게
  if (!isBRotatable) {
    // STEP1. A가 1부터 aLeast 까지
    // 그럼 B 범위는 1 ~ common + bTotal - 1까지
    const case1 = calculator(
      1,
      aLeast,
      1,
      commonTotal + bTotal - 1,
      commonLeast,
      totalSnowCounts,
    );

    // STEP2. A가 aLeast + 1 부터 total - 1까지
    // 그럼 B 범위는 1 ~ total - 1 까지
    const case2 = calculator(
      aLeast + 1,
      totalSnowCounts - 1,
      1,
      totalSnowCounts - 1,
      commonLeast,
      totalSnowCounts,
    );

    return case1 + case2;
  }

  // 이제 둘 다 돌릴수 있는 경우
  /**
   * 일단 범위는 한쪽 기준으로 잡는게 맞는것 같은데.
   * 일단 least가 더 작은쪽이 더 크게 잡는게 맞는듯?
   * 그러면 least가 더 큰쪽은 그냥 순환 없다고 생각하는게 맞나?
   * 모르겠음
   */

  // eslint-disable-next-line no-unused-vars
  let [minLeast, minTotal, maxLeast, maxTotal] =
    aLeast > bLeast
      ? [bLeast, bTotal, aLeast, aTotal]
      : [aLeast, aTotal, bLeast, bTotal];

  // STEP1. min이 1부터 minLeast까지
  // 그럼 max의 범위는 1 ~ common + maxTotal - 1까지
  const case1 = calculator(
    1,
    minLeast,
    1,
    commonTotal + maxTotal - 1,
    commonLeast,
    totalSnowCounts,
  );

  // STEP2. min이 minLeast + 1부터 total - 1까지
  // 그럼 max의 범위는 1 ~ total - 1까지
  const case2 = calculator(
    minLeast + 1,
    totalSnowCounts - 1,
    1,
    totalSnowCounts - 1,
    commonLeast,
    totalSnowCounts,
  );

  return case1 + case2;
}

function solution(grid) {
  grid = grid.map(el => el.split(''));
  const n = grid.length;
  const m = grid[0].length;
  const { start, end } = findStartEnd(n, m, grid);
  const mergedMap = new Array(n).fill().map(() => new Array(m).fill(0));
  fillMergedMap(n, m, grid, start, mergedMap, 1 << 0);
  fillMergedMap(n, m, grid, end, mergedMap, 1 << 1);
  // eslint-disable-next-line no-unused-vars
  const [aCommonRotatable, aCounts] = checkRotatable(
    n,
    m,
    mergedMap,
    (1 << 0) | (1 << 1),
    start,
  );
  const [bCommonRotatable, bCounts] = checkRotatable(
    n,
    m,
    mergedMap,
    (1 << 0) | (1 << 1),
    end,
  );

  const dist = getDist(n, m, grid, start, end);
  const validRootCounts = countValidRoots(grid, n, m, start, end);
  let [isARotateble, aLeast] = checkRotatable(n, m, mergedMap, 1 << 0, start);
  let [isBRotatable, bLeast] = checkRotatable(n, m, mergedMap, 1 << 1, end);

  if (aCommonRotatable) {
      if (isARotateble) {
        aLeast = Math.min(aLeast, aCounts);
      } else {
        aLeast = aCounts;
        isARotateble = true;
      }
  }
  if (bCommonRotatable) {
      if (isBRotatable) {
        bLeast = Math.min(bLeast, bCounts);
      } else {
        bLeast = bCounts;
        isBRotatable = true;
      }
  }
  let { commonTotal, aTotal, bTotal } = getSnowCounts(n, m, mergedMap);
  if (!isARotateble) {
    [isARotateble, aLeast, aTotal, isBRotatable, bLeast, bTotal] = [
      isBRotatable,
      bLeast,
      bTotal,
      isARotateble,
      aLeast,
      aTotal,
    ];
  }

  return calculate(
    isARotateble,
    aLeast,
    aTotal,
    isBRotatable,
    bLeast,
    bTotal,
    // isCommonRotatable,
    dist + 2,
    commonTotal,
    validRootCounts,
  );
}

알파벳 소문자로 이루어진 초기 문자열 s가 주어집니다. 초기 문자열에 포함된 모든 문자들은 고유한 번호를 가지며, n번 문자는 초기 문자열의 n번째 문자를 의미합니다. 예를 들어, 초기 문자열이 "aba"라면 1번 문자는 a, 2번 문자는 b, 3번 문자는 a입니다. 그 후, 초기 문자열에서 1번 문자를 분리해 "a" / "ba" 두 개의 문자열로 나눠졌다면, "a"는 1번 문자로 이루어진 문자열이고 "ba"는 2번 문자와 3번 문자로 이루어진 문자열입니다.

당신은 주어진 문자열에 대해 다음과 같은 5가지 쿼리를 수행해야 합니다. 쿼리는 모두 문자열로 주어집니다.

1 x y : 숫자 1과 정수 x, y가 공백 하나를 사이에 두고 주어집니다. x번 문자와 y번 문자가 같은 문자열에 포함돼 있는지 확인합니다. 같은 문자열에 포함되어 있으면 "YES"를, 포함되어있지 않으면 "NO"를 result 배열의 뒤에 추가합니다. 2 x word : 숫자 2와 정수 x, 문자열 word가 공백 하나를 사이에 두고 주어집니다. x번 문자가 있는 문자열을 찾습니다. 해당 문자열에서 word에 포함된 알파벳을 모두 새로 생성한 빈 문자열로 옮깁니다. 3 x y word : 숫자 3과 정수 x, y가 공백 하나를 사이에 두고 주어집니다. 빈 문자열을 생성한 뒤, x~y번 문자들 중 word에 포함된 알파벳을 모두 새로 생성한 빈 문자열로 옮깁니다. 4 x y : 숫자 4와 정수 x, y가 공백 하나를 사이에 두고 주어집니다. x번 문자가 포함된 문자열과 y번 문자가 포함된 문자열을 하나의 문자열로 합칩니다. 먼저 생성된 문자열에 늦게 생성된 문자열이 합쳐지는 형식으로 먼저 생성된 문자열만 남고 늦게 생성된 문자열은 사라집니다. 5 : 숫자 5가 주어집니다. 항상 쿼리의 마지막에 한 번만 주어집니다. 존재하는 모든 문자열에 대해 문자열의 알파벳 구성을 각각 result 배열의 뒤에 추가합니다. 모든 문자열의 알파벳 구성을 문자열이 먼저 생성된 순으로 result 배열의 뒤에 추가합니다. 유의 사항은 다음과 같습니다.

같은 문자열 안에 있는 문자들은 항상 번호순으로 정렬합니다. 문자열의 길이가 0이 되면 해당 문자열은 사라집니다. 문자열의 알파벳 구성은 다음과 같습니다.

문자열의 알파벳 구성은 하나의 문자열입니다. a부터 z까지 사전 순으로 알파벳과, 해당 알파벳이 문자열에 포함된 개수를 공백 하나로 구분한 형태입니다. 예를 들어, "abaebae" 처럼 a 3개, b 2개, e 2개로 이루어진 문자열의 알파벳 구성은 "a 3 b 2 e 2"입니다. 초기 문자열 s와 쿼리를 담고 있는 문자열 배열 query가 주어집니다. 쿼리를 주어진 순서대로 모두 마친 후의 result 배열을 return 하도록 solution 함수를 완성해 주세요.

풀이

• 각 알파벳(26개)에 대한 위치와, 관계를 SegmentTree와 UnionFind로 구성
• 1번 쿼리: 세그트리에서 조회하고자 하는 ID에 대한 쿼리
  • 해당 ID는 2, 3, 4번 쿼리에 의해 관계가 바뀔 수 있음
  • 해당 바뀐 관계는 UF.find와, updates 배열의 rep값을 참조하여 검색
• 2번 쿼리: 해당 알파벳에 대한 특정 위치에 id값을 검색하여, 해당 id값이 참조하고 있는 updates 배열의 위치 index를 찾아 해당 값을 업데이트 하려는 groupId로 대체
• 3번 쿼리: 해당하는 알파벳 Lazy Segtree에서 해당 범위에 대해 업데이트
• 4번 쿼리: union하려는 두 id값을 모든 세그트리를 순회해서, 만약 큰 id가 updates배열에 없다면 pass하고, 작은id가 없다면 생성 후, map에 등록해주고, uf를 통해 union시킴
  • st.query()가 해당 union을 반영해야 하기 때문에 updates배열 탐색하는 index에 uf.find를 적용

let groupId = 0;

class SegmentTree {
  constructor(n) {
    this.n = n;
    this.tree = new Array(4 * n).fill(0);
    this.lazy = new Array(4 * n).fill(0);
    this.updates = [0];
    this.map = new Map();
    this.map.set(0, 0);

    this.root = new Array(200000).fill().map((_, index) => index);
  }

  mergeRep(x, y) {
    if (!this.map.has(y)) return;
    const yIndex = this._find(this.map.get(y));
    if (!this.map.has(x)) {
      this.updates.push(x);
      this.map.set(x, this.updates.length - 1);
    }
    const xIndex = this._find(this.map.get(x));
    this.root[yIndex] = xIndex;
  }

  _find(x) {
    if (this.root[x] === x) return x;
    return (this.root[x] = this._find(this.root[x]));
  }

  moveRep(x, id) {
    if (!this.map.has(x)) return;
    const updateIndex = this._find(this.map.get(x));
    x = this.updates[updateIndex];
    this.updates[updateIndex] = id;
    this.map.delete(x);
    this.map.set(id, updateIndex);
  }

  _push(node, start, end) {
    if (this.lazy[node] !== 0) {
      this.tree[node] = this.lazy[node];
      if (start !== end) {
        this.lazy[node * 2 + 1] = this.lazy[node];
        this.lazy[node * 2 + 2] = this.lazy[node];
      }
      this.lazy[node] = 0;
    }
  }

  _updateRange(node, start, end, l, r, v) {
    this._push(node, start, end);
    if (end < l || r < start) return;
    if (l <= start && end <= r) {
      this.tree[node] = v;
      if (start !== end) {
        this.lazy[node * 2 + 1] = v;
        this.lazy[node * 2 + 2] = v;
      }
      return;
    }

    const mid = Math.floor((start + end) / 2);
    this._updateRange(node * 2 + 1, start, mid, l, r, v);
    this._updateRange(node * 2 + 2, mid + 1, end, l, r, v);

    const leftVal = this.tree[node * 2 + 1];
    const rightVal = this.tree[node * 2 + 2];
    this.tree[node] = leftVal > rightVal ? leftVal : rightVal;
  }

  updateRange(l, r, id) {
    this.updates.push(id);
    const newIndex = this.updates.length - 1;
    this.map.set(id, newIndex);
    this._updateRange(0, 0, this.n - 1, l, r, newIndex);
  }

  _query(node, start, end, idx) {
    this._push(node, start, end);
    if (start === end) return this.tree[node];
    const mid = Math.floor((start + end) / 2);
    if (idx <= mid) return this._query(node * 2 + 1, start, mid, idx);
    return this._query(node * 2 + 2, mid + 1, end, idx);
  }

  indexQuery(x) {
    return this._query(0, 0, this.n - 1, x);
  }

  query(x) {
    return this.updates[this._find(this.indexQuery(x))];
  }
}

const convertWord = word => word.split('').map(el => el.charCodeAt() - 97);
const ALPHA_LEN = 26;

function solution(s, queries) {
  queries = queries.map(el => el.split(' '));
  s = convertWord(s);
  const n = s.length;
  const sts = new Array(ALPHA_LEN).fill().map(() => new SegmentTree(n));
  const res = [];

  for (const [fl, ...args] of queries) {
    if (fl === '1') {
      const x = +args[0] - 1;
      const y = +args[1] - 1;
      const xid = sts[s[x]].query(x);
      const yid = sts[s[y]].query(y);
      if (xid === yid) res.push('YES');
      else res.push('NO');
    } else if (fl === '2') {
      groupId++;
      const x = +args[0] - 1;
      const word = new Set(convertWord(args[1]));
      const id = sts[s[x]].query(x);
      for (const c of word) {
        sts[c].moveRep(id, groupId);
      }
    } else if (fl === '3') {
      groupId++;
      const x = +args[0] - 1;
      const y = +args[1] - 1;
      const word = new Set(convertWord(args[2]));
      for (const c of word) {
        sts[c].updateRange(x, y, groupId);
      }
    } else if (fl === '4') {
      const x = +args[0] - 1;
      const y = +args[1] - 1;
      let xid = sts[s[x]].query(x);
      let yid = sts[s[y]].query(y);
      if (xid > yid) [xid, yid] = [yid, xid];
      for (const st of sts) {
        st.mergeRep(xid, yid);
      }
    } else if (fl === '5') {
      const bucket = [];
      const collectBox = new Array(groupId + 1)
        .fill()
        .map(() => new Array(26).fill(0));

      for (let x = 0; x < n; x++) {
        const id = sts[s[x]].query(x);
        collectBox[id][s[x]]++;
      }

      for (const collect of collectBox) {
        const box = [];
        for (let i = 0; i < 26; i++) {
          if (!collect[i]) continue;
          box.push(String.fromCharCode(97 + i));
          box.push(collect[i]);
        }
        if (box.length) bucket.push(box.join(' '));
      }
      res.push(...bucket);
    }
  }

  return res;
}

제한 시간: 1 초

N개의 정점이 있다. 차례마다 다음을 반복해서 N개의 정점 사이에 간선을 연결하려고 한다.

먼저 2개의 서로 연결되지 않은 정점 u와 v를 고른다. 그 이후, u가 포함된 연결 요소의 모든 정점들 각각에서, v가 포함된 연결 요소의 모든 정점들 각각으로 간선을 추가한다. 간선의 색은 빨간색 혹은 파란색이다. k번째 차례에 사용할 색깔이 주어질 때, 정점을 골라서 얻을 수 있는 빨간 간선 개수의 최솟값을 구하여라.

입력 첫 번째 줄에 정점의 수 N이 주어진다. 2≤N≤30 두 번째 줄에 각 차례에 사용할 색깔을 표시하는 N−1개의 수가 공백을 구분으로 주어진다. 숫자가 0이면 빨간 간선을, 1이면 파란 간선을 사용한다는 뜻이다. 입력되는 모든 수들은 정수이다. 출력 문제의 조건을 만족하면서 간선을 연결할 때, 얻을 수 있는 빨간 간선 개수의 최솟값을 출력한다.

입력 예시 5 1 1 0 1

출력 예시 1

풀이

• 맨 마지막 상태는 결국 n개의 정점 모두 연결된 상태 {30}

• 맨 마지막 부터 순회하여, 연결 그룹 하나를 잡고, 2개로 나누면서 진행

• 맨 마지막 연결이 파란색(1) 이라면, 힙에 1푸쉬

• 아니라면, 힙의 최소값과 남은 n값을 비교하여, 추가되는 연결 간선 수의 최솟값을 비교하여 연산 진행

  • 만약 힙에서 빠졌다면, 해당값 + 1을 힙에 다시 저장

• O(nlogn)

#include <iostream>
#include <queue>
#include <vector>
using namespace std;

#define FASTIO                 \
  ios::sync_with_stdio(false); \
  cin.tie(NULL);               \
  cout.tie(NULL);

#define F(i, a, b) for (int i = a; i < b; i += 1)
#define FR(i, b, a) for (int i = b; i >= a; i -= 1)

int n;
int result = 0;
vector<int> arr;
priority_queue<int, vector<int>, greater<int>> minHeap;

int main() {
  FASTIO
  cin >> n;
  arr.resize(n - 1);
  F(i, 0, n - 1) cin >> arr[i];

  FR(i, n - 2, 0) {
    if (arr[i] == 1) {
      minHeap.push(1);
    } else {
      const int compare1 = minHeap.size() ? minHeap.top() : 101010101;
      const int compare2 = n - 1;

      if (compare1 <= compare2) {
        result += compare1;
        minHeap.pop();
        minHeap.push(compare1 + 1);
      } else {
        result += compare2;
      }
    }

    n -= 1;
  }

  cout << result;
  return 0;
}

현대모비스의 주행시험장 트랙을 주행해 볼 수 있는 가상 시뮬레이션 프로그램이 있습니다. 시뮬레이션의 트랙에는 1 ~ n의 서로 다른 번호가 붙은 지점이 n개 있으며, 각 지점마다 고유한 스탬프가 있습니다. 각 지점을 방문할 때 해당 지점의 스탬프를 얻을 수 있습니다. 당신은 1번 지점에서 시작하여 각 지점을 최소 한 번씩 방문해 n가지 스탬프를 모두 모으려 합니다.

지점들은 m개의 단방향 도로로 연결되어 있습니다. 당신은 지점 사이를 이동하기 위해 단방향 도로를 이용할 수 있습니다.

다음은 n = 6인 예시입니다.

• 각 원은 지점을 나타내며, 원 안에 적힌 수는 지점의 번호를 나타냅니다.
• 화살표는 두 지점을 연결하고 있는 단방향 도로를 나타냅니다.

위 예시에서 1번 지점에서 출발해 1 - 2 - 6과 같은 경로로 움직이면 1, 2, 6번 지점의 스탬프 3가지를 모을 수 있습니다. 하지만 6번 지점에 도착하면 더 이상 이용할 수 있는 도로가 없습니다.

시뮬레이션에는 단방향 도로를 이용하는 것 외의 이동 방법으로 빠른 이동 기능이 있습니다. 빠른 이동이란 당신이 스탬프를 얻은 지점 중 원하는 곳으로 순간 이동할 수 있는 기능입니다. 예를 들어 위 예시에서 1 - 2 - 6 - 2(빠른 이동) - 4 - 3 - 5와 같은 경로로 움직이면 모든 지점을 한 번씩 방문해 n가지 스탬프를 모두 모을 수 있습니다.

당신은 n가지 스탬프를 모두 모으기 위해 필요한 빠른 이동의 최소 사용 횟수를 알고 싶습니다.

지점의 수를 나타내는 정수 n과 지점을 연결하는 단방향 도로들의 정보를 담고 있는 2차원 정수 배열 roads가 매개변수로 주어집니다. 이때, 1번 지점에서 출발해 n가지 스탬프를 모두 모으기 위해 필요한 빠른 이동의 최소 사용 횟수를 return 하도록 solution 함수를 완성해 주세요.

풀이

/* eslint-disable no-continue */
/* eslint-disable no-param-reassign */
class UnionFind {
  constructor(size) {
    this.parent = new Array(size);
    this.rank = new Array(size);

    for (let i = 0; i < size; i += 1) {
      this.parent[i] = i;
      this.rank[i] = 0;
    }

    this.rank[1] = Infinity;
  }

  find(x) {
    if (this.parent[x] !== x) {
      this.parent[x] = this.find(this.parent[x]);
    }
    return this.parent[x];
  }

  union(x, y) {
    const rootX = this.find(x);
    const rootY = this.find(y);

    if (rootX !== rootY) {
      if (this.rank[rootX] < this.rank[rootY]) {
        this.parent[rootX] = rootY;
      } else if (this.rank[rootX] > this.rank[rootY]) {
        this.parent[rootY] = rootX;
      } else {
        this.parent[rootY] = rootX;
        this.rank[rootX] += 1;
      }
    }
  }

  getUniques() {
    return this.parent.filter((el, index) => (index !== 0 && el === index));
  }
}

function solution(n, roads) {
  const uf = new UnionFind(n + 1);
  const towardGroups = new Array(n + 1).fill().map((_) => []);

  for (const [from, to] of roads) {
    towardGroups[from].push(to);
  }

  const visited = new Array(n + 1).fill(0);
  const stackIndex = new Array(n + 1).fill(null);
  stackIndex[1] = 0;
  visited[1] = 1;

  const dfs = (curIndex, stack) => {
    const towardGroup = towardGroups[curIndex];

    for (const towardIndex of towardGroup) {
      const prefixedTowardIndex = uf.find(towardIndex);
      if (!visited[prefixedTowardIndex]) {
        visited[prefixedTowardIndex] = 1;
        stack.push(prefixedTowardIndex);
        stackIndex[prefixedTowardIndex] = stack.length - 1;
        dfs(prefixedTowardIndex, stack);
        stack.pop();
        stackIndex[prefixedTowardIndex] = null;
      } else {
        const index = stackIndex[prefixedTowardIndex];

        if (index !== null) {
          const value = stack[index];
          const rootValue = uf.find(value);
          uf.rank[rootValue] = Infinity;

          for (let i = index + 1; i < stack.length; i += 1) {
            uf.union(value, stack[i]);
          }
        }
      }
    }
  };

  dfs(1, [1]);

  const prefixTowardGroups = new Array(n + 1).fill().map((_) => []);

  for (const [from, to] of roads) {
    const prefixedFrom = uf.find(from);
    const prefixedTo = uf.find(to);

    if (prefixedFrom !== prefixedTo) {
      prefixTowardGroups[prefixedFrom].push(prefixedTo);
    }
  }

  const towardDirectly = new Array(n + 1);

  const visited2 = new Array(n + 1).fill(0);
  const dfs2 = (x) => {
    let directTowardGroup = new Set();
    visited2[x] = 1;
    const towardGroup = prefixTowardGroups[x];

    for (const toward of towardGroup) {
      directTowardGroup.add(toward);
      if (!visited2[toward]) {
        directTowardGroup = new Set([...directTowardGroup, ...dfs2(toward)]);
      } else {
        directTowardGroup = new Set([...directTowardGroup, ...towardDirectly[toward]]);
      }
    }

    towardDirectly[x] = directTowardGroup;
    return directTowardGroup;
  };

  dfs2(1);

  const uniques = uf.getUniques();
  const fromDirectly = new Array(n + 1).fill().map(() => new Set());

  for (const unique of uniques) {
    for (const el of towardDirectly[unique]) {
      fromDirectly[el].add(unique);
    }
  }

  const assigns = new Array(n + 1).fill(0);

  const bMatching = (x, memo) => {
    const fromGroup = fromDirectly[x];

    for (const from of fromGroup) {
      if (memo[from]) continue;

      memo[from] = 1;

      if (!assigns[from] || bMatching(assigns[from], memo)) {
        assigns[from] = x;

        return true;
      }
    }

    return false;
  };

  let result = 0;

  for (const unique of uniques) {
    if (bMatching(unique, new Array(n + 1).fill(0))) {
      result += 1;
    }
  }
  return uniques.length - result - 1;
}

결과

A와 B가 n개의 주사위를 가지고 승부를 합니다. 주사위의 6개 면에 각각 하나의 수가 쓰여 있으며, 주사위를 던졌을 때 각 면이 나올 확률은 동일합니다. 각 주사위는 1 ~ n의 번호를 가지고 있으며, 주사위에 쓰인 수의 구성은 모두 다릅니다.

A가 먼저 n / 2개의 주사위를 가져가면 B가 남은 n / 2개의 주사위를 가져갑니다. 각각 가져간 주사위를 모두 굴린 뒤, 나온 수들을 모두 합해 점수를 계산합니다. 점수가 더 큰 쪽이 승리하며, 점수가 같다면 무승부입니다.

A는 자신이 승리할 확률이 가장 높아지도록 주사위를 가져가려 합니다.

다음은 n = 4인 예시입니다.

주사위 구성 #1 [1, 2, 3, 4, 5, 6] #2 [3, 3, 3, 3, 4, 4] #3 [1, 3, 3, 4, 4, 4] #4 [1, 1, 4, 4, 5, 5] 예를 들어 A가 주사위 #1, #2를 가져간 뒤 6, 3을 굴리고, B가 주사위 #3, #4를 가져간 뒤 4, 1을 굴린다면 A의 승리입니다. (6 + 3 > 4 + 1) A가 가져가는 주사위 조합에 따라, 주사위를 굴린 1296가지 경우의 승패 결과를 세어보면 아래 표와 같습니다.

A의 주사위 승 무 패 #1, #2 596 196 504 #1, #3 560 176 560 #1, #4 616 184 496 #2, #3 496 184 616 #2, #4 560 176 560 #3, #4 504 196 596 A가 승리할 확률이 가장 높아지기 위해선 주사위 #1, #4를 가져가야 합니다.

주사위에 쓰인 수의 구성을 담은 2차원 정수 배열 dice가 매개변수로 주어집니다. 이때, 자신이 승리할 확률이 가장 높아지기 위해 A가 골라야 하는 주사위 번호를 오름차순으로 1차원 정수 배열에 담아 return 하도록 solution 함수를 완성해 주세요. 승리할 확률이 가장 높은 주사위 조합이 유일한 경우만 주어집니다.

풀이

function solution(dices) {
  const n = dices.length;
  const compareBitNum = 1 << n;
  const groupSize = n / 2;
  const groups = [];

  const dfs = (group, start) => {
    if (group.length === groupSize) {
      groups.push([...group]);
      return;
    }

    if (start === n) return;

    for (let i = start; i < n; i += 1) {
      group.push(i);
      dfs(group, i + 1);
      group.pop();
    }
  };

  dfs([0], 1);

  const getOppoGroup = (group) => {
    const oppoGroup = [];
    const bitGroup = group.reduce((acc, cur) => acc + (1 << cur), 0);
    const bitOppoGroup = ~compareBitNum ^ bitGroup;

    let compare = 0;

    while (compare < n) {
      if (bitOppoGroup & (1 << compare)) oppoGroup.push(compare);

      compare += 1;
    }

    return oppoGroup;
  };

  const oppoGroups = groups.map(getOppoGroup);

  const getBuckets = (group) => {
    const buckets = [];

    const diceConvertGroup = group.map((el) => dices[el]);
    const n = diceConvertGroup.length;
    const m = diceConvertGroup[0].length;

    const dfs = (curN, curValue) => {
      if (curN === n) {
        buckets.push(curValue);
        return;
      }

      for (let i = 0; i < m; i += 1) {
        dfs(curN + 1, curValue + diceConvertGroup[curN][i]);
      }
    };

    dfs(0, 0);
    buckets.sort((a, b) => a - b);

    return buckets;
  };

  const getDupCountMapAndUnique = (arr) => {
    const map = new Map();
    const unique = [];

    for (let i = 0; i < arr.length; i += 1) {
      if (map.has(arr[i])) {
        map.set(arr[i], map.get(arr[i]) + 1);
      } else {
        map.set(arr[i], 1);
        unique.push(arr[i]);
      }
    }

    return { countMap: map, unique };
  };

  const binaryMinIdxSearch = (left, right, arr, target) => {
    if (left > right) return left;

    const mid = Math.floor((left + right) / 2);
    const value = arr[mid];

    if (value < target) {
      return binaryMinIdxSearch(mid + 1, right, arr, target);
    }

    return binaryMinIdxSearch(left, mid - 1, arr, target);
  };

  let maxWins = -1;
  let result = null;

  for (let i = 0; i < groups.length; i += 1) {
    const groupBucket = getBuckets(groups[i]);
    const oppoGroupBucket = getBuckets(oppoGroups[i]);

    const { countMap: groupDupCountMap, unique: groupUnique } = getDupCountMapAndUnique(groupBucket);

    const { countMap: oppoGroupDupCountMap } = getDupCountMapAndUnique(oppoGroupBucket);

    let [totalWin, totalLose] = [0, 0];

    for (const dice of groupUnique) {
      const multiplyPrefix = groupDupCountMap.get(dice);

      const pin1 = binaryMinIdxSearch(0, oppoGroupBucket.length - 1, oppoGroupBucket, dice);
      const draw = oppoGroupDupCountMap.get(dice) || 0;
      const [win, lose] = [pin1, oppoGroupBucket.length - pin1 - draw];

      totalWin += win * multiplyPrefix;
      totalLose += lose * multiplyPrefix;
    }

    const wins = Math.max(totalWin, totalLose);

    if (wins > maxWins) {
      const winningGroup = totalWin > totalLose ? groups[i] : oppoGroups[i];

      maxWins = wins;
      result = winningGroup;
    }
  }

  return result.map((el) => el + 1);
}

결과

당신은 1~n 사이의 수가 적힌 카드가 하나씩 있는 카드 뭉치와 동전 coin개를 이용한 게임을 하려고 합니다. 카드 뭉치에서 카드를 뽑는 순서가 정해져 있으며, 게임은 다음과 같이 진행합니다.

처음에 카드 뭉치에서 카드 n/3장을 뽑아 모두 가집니다. (n은 6의 배수입니다.) 당신은 카드와 교환 가능한 동전 coin개를 가지고 있습니다. 게임은 1라운드부터 시작되며, 각 라운드가 시작할 때 카드를 두 장 뽑습니다. 카드 뭉치에 남은 카드가 없다면 게임을 종료합니다. 뽑은 카드는 카드 한 장당 동전 하나를 소모해 가지거나, 동전을 소모하지 않고 버릴 수 있습니다. 카드에 적힌 수의 합이 n+1이 되도록 카드 두 장을 내고 다음 라운드로 진행할 수 있습니다. 만약 카드 두 장을 낼 수 없다면 게임을 종료합니다. 예를 들어 n = 12, coin = 4이고 [3, 6, 7, 2, 1, 10, 5, 9, 8, 12, 11, 4] 순서대로 카드를 뽑도록 카드 뭉치가 섞여 있습니다.

처음에 3, 6, 7, 2 카드 4장(= n/3)과 동전 4개(= coin)를 가지고 시작합니다. 다음 라운드로 진행하기 위해 내야 할 카드 두 장에 적힌 수의 합은 13(= n+1)입니다. 다음과 같은 방법으로 최대 5라운드까지 도달할 수 있습니다.

1라운드에서 뽑은 카드 1, 10을 동전 두 개를 소모해서 모두 가집니다. 카드 3, 10을 내고 다음 라운드로 진행합니다. 이때 손에 남은 카드는 1, 2, 6, 7이고 동전이 2개 남습니다. 2라운드에서 뽑은 카드 5, 9를 동전을 소모하지 않고 모두 버립니다. 카드 6, 7을 내고 다음 라운드로 진행합니다. 이때 손에 남은 카드는 1, 2고 동전이 2개 남습니다. 3라운드에서 뽑은 카드 8, 12 중 동전 한 개를 소모해서 카드 12를 가집니다. 카드 1, 12을 내고 다음 라운드로 진행합니다. 이때 손에 남은 카드는 2이고 동전이 1개 남습니다. 4라운드에서 뽑은 카드 11, 4 중 동전 한 개를 소모해서 카드 11을 가집니다. 카드 2, 11을 내고 다음 라운드로 진행합니다. 이때 손에 남은 카드와 동전은 없습니다. 5라운드에서 카드 뭉치에 남은 카드가 없으므로 게임을 종료합니다. 처음에 가진 동전수를 나타내는 정수 coin과 카드를 뽑는 순서대로 카드에 적힌 수를 담은 1차원 정수 배열 cards가 매개변수로 주어질 때, 게임에서 도달 가능한 최대 라운드의 수를 return 하도록 solution 함수를 완성해 주세요.

풀이

/* eslint-disable no-param-reassign */
class Heap {
  constructor(compare) {
    this.arr = [];
    this.compare = compare;

    this.getParentIndex = (i) => Math.floor((i - 1) / 2);
    this.getLeftChild = (i) => i * 2 + 1;
    this.getRightChild = (i) => i * 2 + 2;
    this.swap = (idx1, idx2) => {
      [
        [
          this.arr[idx1], this.arr[idx2],
        ],
      ] = [
        [
          this.arr[idx2], this.arr[idx1],
        ],
      ];
    };
  }

  bubbleUp() {
    let index = this.arr.length - 1;
    let parentIndex = this.getParentIndex(index);

    while (index && this.compare(this.arr[parentIndex], this.arr[index])) {
      this.swap(parentIndex, index);
      index = parentIndex;
      parentIndex = this.getParentIndex(index);
    }
  }

  bubbleDown() {
    let index = 0;
    let leftIndex = this.getLeftChild(index);
    let rightIndex = this.getRightChild(index);

    while (
      (this.arr[leftIndex]
        && this.compare(this.arr[index], this.arr[leftIndex])
      ) || (
        this.arr[rightIndex]
        && this.compare(this.arr[index], this.arr[rightIndex])
      )) {
      const targetIndex = (
        this.arr[rightIndex] && this.compare(this.arr[leftIndex], this.arr[rightIndex])
      ) ? rightIndex : leftIndex;

      this.swap(index, targetIndex);

      index = targetIndex;
      leftIndex = this.getLeftChild(index);
      rightIndex = this.getRightChild(index);
    }
  }

  push(x) {
    this.arr.push(x);
    this.bubbleUp();
  }

  pop() {
    if (this.arr.length === 1) return this.arr.pop();

    const value = this.arr[0];
    this.arr[0] = this.arr.pop();
    this.bubbleDown();

    return value;
  }

  size() {
    return this.arr.length;
  }
}

function solution(coin, cards) {
  const minHeap = new Heap((parent, child) => parent > child);
  const maxHeap = new Heap((parent, child) => parent < child);

  const discardedCards = new Array(cards.length + 1).fill(false);
  const onHandCards = new Array(cards.length + 1).fill(false);
  const initHandCards = new Array(cards.length + 1).fill(false);

  const indexMap = cards
    .map((card, index) => [card, index])
    .sort((a, b) => a[0] - b[0])
    .map((info) => info[1]);

  const getOppositeCardIndex = (cardIndex) => indexMap[cards.length - cards[cardIndex]];
  const getOppositeCard = (cardIndex) => cards.length + 1 - cards[cardIndex];
  const initSize = cards.length / 3;

  let result = 1;
  let couples = 0;

  for (let i = 0; i < initSize; i += 1) {
    if (!discardedCards[cards[i]]) {
      if (getOppositeCardIndex(i) < initSize) {
        couples += 1;
        discardedCards[cards[i]] = true;
        discardedCards[getOppositeCard(i)] = true;
      } else {
        onHandCards[cards[i]] = true;
        initHandCards[cards[i]] = true;
      }
    }
  }

  const getCouples = () => {
    while (minHeap.size()) {
      const minIndex = minHeap.pop();
      const oppoCard = cards[minIndex];
      const card = cards[getOppositeCardIndex(minIndex)];

      if (onHandCards[card] && onHandCards[oppoCard]) {
        couples += 1;

        discardedCards[card] = true;
        onHandCards[card] = false;

        discardedCards[oppoCard] = true;
        onHandCards[oppoCard] = false;

        break;
      }
    }
  };

  const getCoin = () => {
    while (maxHeap.size()) {
      const maxIndex = maxHeap.pop();
      const oppoCard = cards[maxIndex];
      const card = cards[getOppositeCardIndex(maxIndex)];

      if (onHandCards[card] && !initHandCards[card]) {
        coin += 1;

        discardedCards[card] = true;
        onHandCards[card] = false;

        if (onHandCards[oppoCard] && !initHandCards[oppoCard]) {
          coin += 1;

          onHandCards[oppoCard] = false;
        }

        discardedCards[oppoCard] = true;

        break;
      }
    }
  };

  for (let i = initSize; i < cards.length; i += 2) {
    if (!discardedCards[getOppositeCard(i)]
    && !discardedCards[cards[i]]) {
      onHandCards[cards[i]] = true;
      minHeap.push(getOppositeCardIndex(i));
      maxHeap.push(getOppositeCardIndex(i));
      coin -= 1;
    }

    if (!discardedCards[getOppositeCard(i + 1)]
    && !discardedCards[cards[i + 1]]) {
      onHandCards[cards[i + 1]] = true;
      minHeap.push(getOppositeCardIndex(i + 1));
      maxHeap.push(getOppositeCardIndex(i + 1));
      coin -= 1;
    }

    while (coin < 0) {
      getCoin();
    }

    if (!couples) getCouples();

    if (!couples) {
      break;
    }

    result += 1;
    couples -= 1;
  }

  return result;
}

결과

첫 솔브 기념

한 변의 길이가 1인 정삼각형 2n+1개를 이어붙여 윗변의 길이가 n, 아랫변의 길이가 n+1인 사다리꼴을 만들 수 있습니다. 이때 사다리꼴의 윗변과 변을 공유하는 n개의 정삼각형 중 일부의 위쪽에 같은 크기의 정삼각형을 붙여 새로운 모양을 만들었습니다. 예를 들어 n이 4이고, 1번째, 2번째, 4번째 정삼각형 위에 정삼각형을 붙인 모양은 다음과 같습니다.

이렇게 만든 모양을 정삼각형 타일 또는 정삼각형 2개를 이어 붙인 마름모 타일로 빈 곳이 없도록 채우려고 합니다. 정삼각형 타일과 마름모 타일은 돌려서 사용할 수 있습니다.

타일을 놓을 때 다른 타일과 겹치거나 모양을 벗어나게 놓을 수는 없습니다. 위의 예시 모양을 채우는 방법 중 일부는 다음과 같습니다.

사다리꼴의 윗변의 길이를 나타내는 정수 n과 사다리꼴 윗변에 붙인 정삼각형을 나타내는 1차원 정수 배열 tops가 매개변수로 주어집니다. 이때 문제 설명에 따라 만든 모양을 정삼각형 또는 마름모 타일로 빈 곳이 없도록 채우는 경우의 수를 10007로 나눈 나머지를 return 하도록 solution 함수를 완성해 주세요.

풀이

function solution(n, tops) {
  const MOD = 10007;
  const dp = new Array(n + 1).fill().map(() => new Array(2).fill(0));

  dp[0][0] = 1;

  for (let i = 0; i < n; i += 1) {
    if (tops[i]) {
      dp[i + 1][0] = dp[i][0] * 3 + dp[i][1] * 2;
    } else {
      dp[i + 1][0] = dp[i][0] * 2 + dp[i][1] * 1;
    }

    dp[i + 1][1] = dp[i][0] + dp[i][1];

    dp[i + 1][0] %= MOD;
    dp[i + 1][1] %= MOD;
  }

  return (dp[n][0] + dp[n][1]) % MOD;
}

결과

풀이 1(bfs)

const fs = require('fs');

const input = fs.readFileSync('/dev/stdin').toString().trim().split('\n');
let [N, K] = input[0].split(' ').map(Number);

const visit = (pos, queue, visited) => {
  visited[pos] = true;
  queue.push(pos);
};

if (N >= K) {
  console.log(N - K);
} else {
  const maxSize = K * 2 + 1;
  const visited = new Array(maxSize).fill(false);

  let result = 0;
  let queue = [N];
  visited[N] = true;

  while (queue.length) {
    const newQueue = [];
    let isBreak = false;

    for (const pos of queue) {
      if (pos === K) {
        isBreak = true;
        break;
      }

      if (pos !== 0) {
        let posCache = pos * 2;

        while (posCache < maxSize) {
          if (!visited[posCache]) {
            visit(posCache, queue, visited);
          }

          posCache *= 2;
        }
      }
    }

    for (const pos of queue) {
      if (pos + 1 < maxSize && !visited[pos + 1]) {
        visit(pos + 1, newQueue, visited);
      }

      if (pos - 1 >= 0 && !visited[pos - 1]) {
        visit(pos - 1, newQueue, visited);
      }
    }

    if (isBreak) break;

    result += 1;

    queue = newQueue;
  }

  console.log(result);
}

결과 1

풀이 2(bitmasking)

const fs = require('fs');

const input = fs.readFileSync(
  process.env.LOGNAME === 'jake' ? './input.txt' : '/dev/stdin',
).toString().trim().split('\n');

let [N, K] = input[0].split(' ').map(Number);

if (N >= K) {
  console.log(N - K);
} else {
  let result = 0;

  if (N === 0) {
    result += 1;
    N += 1;
  }

  const getCount = (num, length) => {
    let count = 0;

    const prefix = num >> (length - 1);

    count += prefix;

    num ^= (prefix << (length - 1));

    while (num) {
      while (!(num & 1)) {
        num >>= 1;
      }

      if ((num & 2)) {
        num += 1;
      }

      num >>= 2;
      count += 1;
    }

    return count;
  };

  let length = 1;
  while (N < K) {
    length += 1;
    N <<= 1;
  }

  const num1 = N - K;
  const num2 = K - (N >> 1);

  const count1 = getCount(num1, length);
  const count2 = getCount(num2, length - 1);

  console.log(result + Math.min(count1, count2));
}

결과 2

N개의 마을로 이루어진 나라가 있습니다. 이 나라의 각 마을에는 1부터 N까지의 번호가 각각 하나씩 부여되어 있습니다. 각 마을은 양방향으로 통행할 수 있는 도로로 연결되어 있는데, 서로 다른 마을 간에 이동할 때는 이 도로를 지나야 합니다. 도로를 지날 때 걸리는 시간은 도로별로 다릅니다. 현재 1번 마을에 있는 음식점에서 각 마을로 음식 배달을 하려고 합니다. 각 마을로부터 음식 주문을 받으려고 하는데, N개의 마을 중에서 K 시간 이하로 배달이 가능한 마을에서만 주문을 받으려고 합니다. 다음은 N = 5, K = 3인 경우의 예시입니다.

위 그림에서 1번 마을에 있는 음식점은 [1, 2, 4, 5] 번 마을까지는 3 이하의 시간에 배달할 수 있습니다. 그러나 3번 마을까지는 3시간 이내로 배달할 수 있는 경로가 없으므로 3번 마을에서는 주문을 받지 않습니다. 따라서 1번 마을에 있는 음식점이 배달 주문을 받을 수 있는 마을은 4개가 됩니다. 마을의 개수 N, 각 마을을 연결하는 도로의 정보 road, 음식 배달이 가능한 시간 K가 매개변수로 주어질 때, 음식 주문을 받을 수 있는 마을의 개수를 return 하도록 solution 함수를 완성해주세요.

풀이

function solution(N, road, K) {
    const dp = new Array(N).fill().map(_ => new Array(N).fill(Infinity));

    for (let i = 0; i < N; i += 1) dp[i][i] = 0;

    const recursive = (start, end, value) => {
        if (value > K) return; // 문제 효율성을 위한 처리 (채워진 그래프를 원할 시 삭제)

        if (dp[start][end] > value) {
            dp[start][end] = value;
            dp[end][start] = value;

            for (let i = 0; i < N; i += 1) {
                if (i !== end && i !== start) {
                    recursive(start, i, dp[end][i] + value);
                    recursive(i, end, dp[start][i] + value);
                }
            }
        }
    }

    for (const [start, end, value] of road) {
        recursive(start - 1, end - 1, value);
    }

    return dp[0].filter(el => el <= K).length;
}

결과

n x m 크기 격자 모양의 퍼즐판이 주어집니다.

퍼즐판에는 빨간색 수레와 파란색 수레가 하나씩 존재합니다. 각 수레들은 자신의 시작 칸에서부터 자신의 도착 칸까지 이동해야 합니다. 모든 수레들을 각자의 도착 칸으로 이동시키면 퍼즐을 풀 수 있습니다.

당신은 각 턴마다 반드시 모든 수레를 상하좌우로 인접한 칸 중 한 칸으로 움직여야 합니다. 단, 수레를 움직일 때는 아래와 같은 규칙이 있습니다.

수레는 벽이나 격자 판 밖으로 움직일 수 없습니다. 수레는 자신이 방문했던 칸으로 움직일 수 없습니다. 자신의 도착 칸에 위치한 수레는 움직이지 않습니다. 계속 해당 칸에 고정해 놓아야 합니다. 동시에 두 수레를 같은 칸으로 움직일 수 없습니다. 수레끼리 자리를 바꾸며 움직일 수 없습니다. 예를 들어, 아래 그림처럼 n = 3, m = 2인 퍼즐판이 있습니다.

속이 빨간색인 원은 빨간색 수레를 나타냅니다. 속이 파란색인 원은 파란색 수레를 나타냅니다. 테두리가 빨간색인 원은 빨간색 수레의 도착 칸을 나타냅니다. 테두리가 파란색인 원은 파란색 수레의 도착 칸을 나타냅니다. 위 퍼즐판은 아래와 같은 순서로 3턴만에 풀 수 있습니다.

빨간색 사선이 처진 칸은 빨간색 수레가 방문했던 칸을 나타냅니다. 규칙에 따라 빨간색 수레는 빨간색 사선이 처진 칸(방문했던 칸)으로는 이동할 수 없습니다. 파란색 사선이 처진 칸은 파란색 수레가 방문했던 칸을 나타냅니다. 규칙에 따라 파란색 수레는 파란색 사선이 처진 칸(방문했던 칸)으로는 이동할 수 없습니다.

위처럼 동시에 수레를 같은 칸으로 움직일 수는 없습니다. 퍼즐판의 정보를 나타내는 2차원 정수 배열 maze가 매개변수로 주어집니다. 퍼즐을 푸는데 필요한 턴의 최솟값을 return 하도록 solution 함수를 완성해 주세요. 퍼즐을 풀 수 없는 경우 0을 return 해주세요.

풀이

function solution(maze) {
  const colLen = maze.length;
  const rowLen = maze[0].length;
  const pos = [null, null, null, null];
  const dest = [null, null, null, null];
  const redVisited = new Array(colLen)
    .fill()
    .map(_ => new Array(rowLen).fill(false));
  const blueVisited = new Array(colLen)
    .fill()
    .map(_ => new Array(rowLen).fill(false));
  const moves = [
    [1, 0],
    [-1, 0],
    [0, 1],
    [0, -1],
  ];

  for (let i = 0; i < colLen; i += 1) {
    for (let j = 0; j < rowLen; j += 1) {
      if (maze[i][j] === 1) {
        pos[0] = i;
        pos[1] = j;
        redVisited[i][j] = true;
      } else if (maze[i][j] === 2) {
        pos[2] = i;
        pos[3] = j;
        blueVisited[i][j] = true;
      } else if (maze[i][j] === 3) {
        dest[0] = i;
        dest[1] = j;
      } else if (maze[i][j] === 4) {
        dest[2] = i;
        dest[3] = j;
      }
    }
  }

  const posQueue = [pos];

  const getValidMoves = (x, y, isRed) => {
    const visited = isRed ? redVisited : blueVisited;
    const validMoves = [];

    for (const [dx, dy] of moves) {
      const [movedX, movedY] = [x + dx, y + dy];

      if (
        movedX >= 0 &&
        movedX < colLen &&
        movedY >= 0 &&
        movedY < rowLen &&
        maze[movedX][movedY] !== 5 &&
        !visited[movedX][movedY]
      ) {
        validMoves.push([movedX, movedY]);
      }
    }

    return validMoves;
  };

  const recursive = ([rx, ry, bx, by], count) => {
    if (rx === dest[0] && ry === dest[1] && bx === dest[2] && by === dest[3])
      return count;

    const redMoves =
      rx === dest[0] && ry === dest[1]
        ? [[rx, ry]]
        : getValidMoves(rx, ry, true);
    const blueMoves =
      bx === dest[2] && by === dest[3] ? [[bx, by]] : getValidMoves(bx, by);

    const min = [Infinity];

    for (const [rmx, rmy] of redMoves) {
      for (const [bmx, bmy] of blueMoves) {
        if (
          !(rmx === bx && rmy === by && bmx === rx && bmy === ry) &&
          !(rmx === bmx && rmy === bmy)
        ) {
          redVisited[rmx][rmy] = true;
          blueVisited[bmx][bmy] = true;
          min.push(recursive([rmx, rmy, bmx, bmy], count + 1));
          redVisited[rmx][rmy] = false;
          blueVisited[bmx][bmy] = false;
        }
      }
    }

    return Math.min(...min);
  };

  const result = recursive(pos, 0);

  return result === Infinity ? 0 : result;
}

결과

시침, 분침, 초침이 있는 아날로그시계가 있습니다. 시계의 시침은 12시간마다, 분침은 60분마다, 초침은 60초마다 시계를 한 바퀴 돕니다. 따라서 시침, 분침, 초침이 움직이는 속도는 일정하며 각각 다릅니다. 이 시계에는 초침이 시침/분침과 겹칠 때마다 알람이 울리는 기능이 있습니다. 당신은 특정 시간 동안 알람이 울린 횟수를 알고 싶습니다.

다음은 0시 5분 30초부터 0시 7분 0초까지 알람이 울린 횟수를 세는 예시입니다.

가장 짧은 바늘이 시침, 중간 길이인 바늘이 분침, 가장 긴 바늘이 초침입니다. 알람이 울리는 횟수를 세기 시작한 시각은 0시 5분 30초입니다. 이후 0시 6분 0초까지 초침과 시침/분침이 겹치는 일은 없습니다.

약 0시 6분 0.501초에 초침과 시침이 겹칩니다. 이때 알람이 한 번 울립니다. 이후 0시 6분 6초까지 초침과 시침/분침이 겹치는 일은 없습니다.

약 0시 6분 6.102초에 초침과 분침이 겹칩니다. 이때 알람이 한 번 울립니다. 이후 0시 7분 0초까지 초침과 시침/분침이 겹치는 일은 없습니다. 0시 5분 30초부터 0시 7분 0초까지는 알람이 두 번 울립니다. 이후 약 0시 7분 0.584초에 초침과 시침이 겹쳐서 울리는 세 번째 알람은 횟수에 포함되지 않습니다.

다음은 12시 0분 0초부터 12시 0분 30초까지 알람이 울린 횟수를 세는 예시입니다.

알람이 울리는 횟수를 세기 시작한 시각은 12시 0분 0초입니다. 초침과 시침, 분침이 겹칩니다. 이때 알람이 한 번 울립니다. 이와 같이 0시 정각, 12시 정각에 초침과 시침, 분침이 모두 겹칠 때는 알람이 한 번만 울립니다.

이후 12시 0분 30초까지 초침과 시침/분침이 겹치는 일은 없습니다. 12시 0분 0초부터 12시 0분 30초까지는 알람이 한 번 울립니다.

알람이 울리는 횟수를 센 시간을 나타내는 정수 h1, m1, s1, h2, m2, s2가 매개변수로 주어집니다. 이때, 알람이 울리는 횟수를 return 하도록 solution 함수를 완성해주세요.

풀이

function solution(h1, m1, s1, h2, m2, s2) {
  const getCount = (h, m, s) => {
    let [mCount, hCount] = [0, 0];

    mCount += h * 59;
    hCount += h * 60;

    let result = 0;

    mCount += m;
    hCount += m;
    result -= 1;

    const curMDegree = m * 6;
    const curHDegree = 30 * (h % 12) + 0.5 * m;
    const condition1 = curMDegree <= 5.9 * s;
    const condition2 = curHDegree <= (6 - 1 / 120) * s;

    if (condition1) mCount += 1;
    if (condition2) hCount += 1;

    if (h >= 12) {
      hCount -= 1;
      result -= 1;
    }

    result += mCount + hCount;

    return result;
  };

  let result = getCount(h2, m2, s2) - getCount(h1, m1, s1);
  if (s1 === 0 && m1 === 0) result += 1;

  return result;
}

결과

세로길이가 n 가로길이가 m인 격자 모양의 땅 속에서 석유가 발견되었습니다. 석유는 여러 덩어리로 나누어 묻혀있습니다. 당신이 시추관을 수직으로 단 하나만 뚫을 수 있을 때, 가장 많은 석유를 뽑을 수 있는 시추관의 위치를 찾으려고 합니다. 시추관은 열 하나를 관통하는 형태여야 하며, 열과 열 사이에 시추관을 뚫을 수 없습니다.

예를 들어 가로가 8, 세로가 5인 격자 모양의 땅 속에 위 그림처럼 석유가 발견되었다고 가정하겠습니다. 상, 하, 좌, 우로 연결된 석유는 하나의 덩어리이며, 석유 덩어리의 크기는 덩어리에 포함된 칸의 수입니다. 그림에서 석유 덩어리의 크기는 왼쪽부터 8, 7, 2입니다.

시추관은 위 그림처럼 설치한 위치 아래로 끝까지 뻗어나갑니다. 만약 시추관이 석유 덩어리의 일부를 지나면 해당 덩어리에 속한 모든 석유를 뽑을 수 있습니다. 시추관이 뽑을 수 있는 석유량은 시추관이 지나는 석유 덩어리들의 크기를 모두 합한 값입니다. 시추관을 설치한 위치에 따라 뽑을 수 있는 석유량은 다음과 같습니다.

시추관의 위치 획득한 덩어리 총 석유량 1 [8] 8 2 [8] 8 3 [8] 8 4 [7] 7 5 [7] 7 6 [7] 7 7 [7, 2] 9 8 [2] 2 오른쪽 그림처럼 7번 열에 시추관을 설치하면 크기가 7, 2인 덩어리의 석유를 얻어 뽑을 수 있는 석유량이 9로 가장 많습니다.

석유가 묻힌 땅과 석유 덩어리를 나타내는 2차원 정수 배열 land가 매개변수로 주어집니다. 이때 시추관 하나를 설치해 뽑을 수 있는 가장 많은 석유량을 return 하도록 solution 함수를 완성해 주세요.

풀이

function solution(land) {
  const n = land.length;
  const m = land[0].length;
  const moves = [
    [1, 0],
    [-1, 0],
    [0, 1],
    [0, -1],
  ];
  const dp = new Array(m + 1).fill(0);

  const bfs = (moveGroup, landObj) => {
    const newMoveGroup = [];
    landObj.area += moveGroup.length;

    for (const [i, j] of moveGroup) {
      if (landObj.maxJ < j) landObj.maxJ = j;
      if (landObj.minJ > j) landObj.minJ = j;

      for (const [mi, mj] of moves) {
        const [movedI, movedJ] = [mi + i, mj + j];
        if (
          movedI < n &&
          movedI >= 0 &&
          movedJ < m &&
          movedJ >= 0 &&
          land[movedI][movedJ]
        ) {
          land[movedI][movedJ] = 0;
          newMoveGroup.push([movedI, movedJ]);
        }
      }
    }

    if (newMoveGroup.length) bfs(newMoveGroup, landObj);
  };

  for (let i = 0; i < n; i += 1) {
    for (let j = 0; j < m; j += 1) {
      if (land[i][j]) {
        const landObj = { area: 0, minJ: j, maxJ: j };
        land[i][j] = 0;
        bfs([[i, j]], landObj);

        dp[landObj.minJ] += landObj.area;
        dp[landObj.maxJ + 1] -= landObj.area;
      }
    }
  }

  let sum = 0;
  let result = 0;

  for (let i = 0; i < m; i += 1) {
    if (dp[i]) {
      sum += dp[i];

      if (sum > result) result = sum;
    }
  }

  return result;
}

결과

어떤 게임에는 붕대 감기라는 기술이 있습니다.

붕대 감기는 t초 동안 붕대를 감으면서 1초마다 x만큼의 체력을 회복합니다. t초 연속으로 붕대를 감는 데 성공한다면 y만큼의 체력을 추가로 회복합니다. 게임 캐릭터에는 최대 체력이 존재해 현재 체력이 최대 체력보다 커지는 것은 불가능합니다.

기술을 쓰는 도중 몬스터에게 공격을 당하면 기술이 취소되고, 공격을 당하는 순간에는 체력을 회복할 수 없습니다. 몬스터에게 공격당해 기술이 취소당하거나 기술이 끝나면 그 즉시 붕대 감기를 다시 사용하며, 연속 성공 시간이 0으로 초기화됩니다.

몬스터의 공격을 받으면 정해진 피해량만큼 현재 체력이 줄어듭니다. 이때, 현재 체력이 0 이하가 되면 캐릭터가 죽으며 더 이상 체력을 회복할 수 없습니다.

당신은 붕대감기 기술의 정보, 캐릭터가 가진 최대 체력과 몬스터의 공격 패턴이 주어질 때 캐릭터가 끝까지 생존할 수 있는지 궁금합니다.

붕대 감기 기술의 시전 시간, 1초당 회복량, 추가 회복량을 담은 1차원 정수 배열 bandage와 최대 체력을 의미하는 정수 health, 몬스터의 공격 시간과 피해량을 담은 2차원 정수 배열 attacks가 매개변수로 주어집니다. 모든 공격이 끝난 직후 남은 체력을 return 하도록 solution 함수를 완성해 주세요. 만약 몬스터의 공격을 받고 캐릭터의 체력이 0 이하가 되어 죽는다면 -1을 return 해주세요.

풀이

function solution(bandage, health, attacks) {
    const maxHealth = health;
    const [t, x, y] = bandage;

    let lastAttackTime = 0;

    for (const [attackTime, damage] of attacks) {
        const timeDiff = attackTime - lastAttackTime - 1;
        const heal = timeDiff * x + Math.floor(timeDiff / t) * y;
        health = Math.min(health + heal, maxHealth);

        health -= damage;

        if (health <= 0) return -1;

        lastAttackTime = attackTime;
    }

    return health;
}

결과

풀이

const fs = require('fs');

const input = fs.readFileSync('/dev/stdin').toString().trim().split('\n');
const [N, M] = input[0].split(' ').map(Number);
const A = input[1].split(' ').map(Number);
const B = input[2].split(' ').map(Number);

class SegmentTree {
  constructor(arr) {
    this.arr = arr;
    this.tree = new Array(arr.length * 4);
    this.build(0, 0, arr.length - 1);
  }

  build(node, left, right) {
    if (left === right) {
      this.tree[node] = this.arr[left];
    } else {
      const mid = Math.floor((left + right) / 2);
      const leftChild = node * 2 + 1;
      const rightChild = node * 2 + 2;
      this.build(leftChild, left, mid);
      this.build(rightChild, mid + 1, right);
      this.tree[node] = Math.max(this.tree[leftChild], this.tree[rightChild]);
    }
  }

  query(node, left, right, queryLeft, queryRight) {
    if (left > queryRight || right < queryLeft) {
      return -Infinity;
    }

    if (left >= queryLeft && right <= queryRight) {
      return this.tree[node];
    }

    const mid = Math.floor((left + right) / 2);
    const leftChild = node * 2 + 1;
    const rightChild = node * 2 + 2;
    const leftValue = this.query(leftChild, left, mid, queryLeft, queryRight);
    const rightValue = this.query(rightChild, mid + 1, right, queryLeft, queryRight);

    return Math.max(leftValue, rightValue);
  }

  update(node, left, right, index, newValue) {
    if (left === right) {
      this.arr[index] = newValue;
      this.tree[node] = newValue;
    } else {
      const mid = Math.floor((left + right) / 2);
      const leftChild = node * 2 + 1;
      const rightChild = node * 2 + 2;

      if (index <= mid) {
        this.update(leftChild, left, mid, index, newValue);
      } else {
        this.update(rightChild, mid + 1, right, index, newValue);
      }

      this.tree[node] = Math.max(this.tree[leftChild], this.tree[rightChild]);
    }
  }
}

if (N < M) {
  console.log(A.reduce((acc, cur) => acc + cur, 0));
} else if (N === M) {
  console.log(A.reduce((acc, cur) => acc + cur, 0) + B[M - 1]);
} else {
  const sum = [...A];

  for (let i = 1; i < N; i += 1) {
    sum[i] += sum[i - 1];
  }

  const dp = new Array(N).fill(-Infinity);
  const treeArr = new Array(N).fill(-Infinity);

  dp[0] = -A[0];
  treeArr[0] = -A[0] - sum[0];

  const MaxSegTree = new SegmentTree(treeArr);

  for (let i = 1; i < N; i += 1) {
    const dpMax = i - M >= 0
      ? MaxSegTree.query(0, 0, N - 1, i - M, i - 1)
      : 0;

    dp[i] = dpMax + sum[i - 1] - A[i];
    MaxSegTree.update(0, 0, N - 1, i, dp[i] - sum[i]);
  }

  let result = sum[M - 1] + B[M - 1];

  for (let i = 0; i < N - M; i += 1) {
    result = Math.max(result, sum[i + M] - sum[i] + dp[i] + B[i + M]);
  }

  for (let i = Math.max(0, N - M); i < N; i += 1) {
    result = Math.max(result, sum[N - 1] - sum[i] + dp[i]);
  }

  console.log(result);
}

결과

현대모비스는 우수한 SW 인재 채용을 위해 상시로 채용 설명회를 진행하고 있습니다. 채용 설명회에서는 채용과 관련된 상담을 원하는 참가자에게 멘토와 1:1로 상담할 수 있는 기회를 제공합니다. 채용 설명회에는 멘토 n명이 있으며, 1~k번으로 분류되는 상담 유형이 있습니다. 각 멘토는 k개의 상담 유형 중 하나만 담당할 수 있습니다. 멘토는 자신이 담당하는 유형의 상담만 가능하며, 다른 유형의 상담은 불가능합니다. 멘토는 동시에 참가자 한 명과만 상담 가능하며, 상담 시간은 정확히 참가자가 요청한 시간만큼 걸립니다.

참가자가 상담 요청을 하면 아래와 같은 규칙대로 상담을 진행합니다.

상담을 원하는 참가자가 상담 요청을 했을 때, 참가자의 상담 유형을 담당하는 멘토 중 상담 중이 아닌 멘토와 상담을 시작합니다. 만약 참가자의 상담 유형을 담당하는 멘토가 모두 상담 중이라면, 자신의 차례가 올 때까지 기다립니다. 참가자가 기다린 시간은 참가자가 상담 요청했을 때부터 멘토와 상담을 시작할 때까지의 시간입니다. 모든 멘토는 상담이 끝났을 때 자신의 상담 유형의 상담을 받기 위해 기다리고 있는 참가자가 있으면 즉시 상담을 시작합니다. 이때, 먼저 상담 요청한 참가자가 우선됩니다. 참가자의 상담 요청 정보가 주어질 때, 참가자가 상담을 요청했을 때부터 상담을 시작하기까지 기다린 시간의 합이 최소가 되도록 각 상담 유형별로 멘토 인원을 정하려 합니다. 단, 각 유형별로 멘토 인원이 적어도 한 명 이상이어야 합니다.

예를 들어, 5명의 멘토가 있고 1~3번의 3가지 상담 유형이 있을 때 아래와 같은 참가자의 상담 요청이 있습니다.

참가자의 상담 요청

참가자 번호 시각 상담 시간 상담 유형 1번 참가자 10분 60분 1번 유형 2번 참가자 15분 100분 3번 유형 3번 참가자 20분 30분 1번 유형 4번 참가자 30분 50분 3번 유형 5번 참가자 50분 40분 1번 유형 6번 참가자 60분 30분 2번 유형 7번 참가자 65분 30분 1번 유형 8번 참가자 70분 100분 2번 유형 이때, 멘토 인원을 아래와 같이 정하면, 참가자가 기다린 시간의 합이 25로 최소가 됩니다.

1번 유형 2번 유형 3번 유형 2명 1명 2명

1번 유형

1번 유형을 담당하는 멘토가 2명 있습니다.

1번 참가자가 상담 요청했을 때, 멘토#1과 10분70분 동안 상담을 합니다. 3번 참가자가 상담 요청했을 때, 멘토#2와 20분50분 동안 상담을 합니다. 5번 참가자가 상담 요청했을 때, 멘토#2와 50분90분 동안 상담을 합니다. 7번 참가자가 상담 요청했을 때, 모든 멘토가 상담 중이므로 1번 참가자의 상담이 끝날 때까지 5분 동안 기다리고 멘토#1과 70분100분 동안 상담을 합니다.

2번 유형

2번 유형을 담당하는 멘토가 1명 있습니다.

6번 참가자가 상담 요청했을 때, 멘토와 60분90분 동안 상담을 합니다. 8번 참가자가 상담 요청했을 때, 모든 멘토가 상담 중이므로 6번 참가자의 상담이 끝날 때까지 20분 동안 기다리고 90분190분 동안 상담을 합니다.

3번 유형

3번 유형을 담당하는 멘토가 2명 있습니다.

2번 참가자가 상담 요청했을 때, 멘토#1과 15분115분 동안 상담을 합니다. 4번 참가자가 상담 요청했을 때, 멘토#2와 30분80분 동안 상담을 합니다. 상담 유형의 수를 나타내는 정수 k, 멘토의 수를 나타내는 정수 n과 참가자의 상담 요청을 담은 2차원 정수 배열 reqs가 매개변수로 주어집니다. 멘토 인원을 적절히 배정했을 때 참가자들이 상담을 받기까지 기다린 시간을 모두 합한 값의 최솟값을 return 하도록 solution 함수를 완성해 주세요.

풀이

function solution(k, n, reqs) {
  const typeReqs = new Array(k).fill().map((_) => []);
  const dps = new Array(k).fill().map((_) => new Array(n).fill(null));

  for (const req of reqs) {
    typeReqs[req[2] - 1].push([req[0], req[1]]);
  }

  for (const typeReq of typeReqs) {
    typeReq.sort((a, b) => a[0] - b[0]);
  }

  for (let i = 0; i < k; i += 1) {
    const typeReq = typeReqs[i];
    const dp = dps[i];

    for (let j = 0; j < n; j += 1) {
      const memo = new Array(j + 1).fill(0);
      let result = 0;

      for (const oneTypeReq of typeReq) {
        const [start, spend] = oneTypeReq;

        let min = Infinity;
        let minIndex = null;

        for (let l = 0; l < j + 1; l += 1) {
          const value = memo[l];

          if (value < min) {
            min = value;
            minIndex = l;
          }
        }

        if (min < start) {
          memo[minIndex] = start + spend;
        } else {
          result += min - start;
          memo[minIndex] += spend;
        }
      }

      dp[j] = result;
    }
  }

  let remainTutorCount = n - k;

  const tutorCounts = new Array(k).fill(1);

  while (remainTutorCount) {
    let max = -Infinity;
    let maxIndex = null;

    for (let i = 0; i < k; i += 1) {
      const dp = dps[i];
      const count = tutorCounts[i];
      const calculated = dp[count - 1] - dp[count];

      if (max < calculated) {
        max = calculated;
        maxIndex = i;
      }
    }

    tutorCounts[maxIndex] += 1;
    remainTutorCount -= 1;
  }

  let result = 0;

  for (let i = 0; i < k; i += 1) {
    result += dps[i][tutorCounts[i] - 1];
  }

  return result;
}

결과

x축과 y축으로 이루어진 2차원 직교 좌표계에 중심이 원점인 서로 다른 크기의 원이 두 개 주어집니다. 반지름을 나타내는 두 정수 r1, r2가 매개변수로 주어질 때, 두 원 사이의 공간에 x좌표와 y좌표가 모두 정수인 점의 개수를 return하도록 solution 함수를 완성해주세요. ※ 각 원 위의 점도 포함하여 셉니다.

풀이

function solution(r1, r2) {
  let result = 0;
  let curMaxY = r2;
  let curMinY = r1;

  for (let i = 0; i <= r2; i += 1) {
    while (curMaxY ** 2 + i ** 2 > r2 ** 2) curMaxY -= 1;
    while (curMinY !== -1 && (curMinY ** 2 + i ** 2 >= r1 ** 2)) curMinY -= 1;

    result += curMaxY - curMinY;
  }

  return result * 4 - (r2 - r1 + 1) * 4;
}

결과

A 나라가 B 나라를 침공하였습니다. B 나라의 대부분의 전략 자원은 아이기스 군사 기지에 집중되어 있기 때문에 A 나라는 B 나라의 아이기스 군사 기지에 융단폭격을 가했습니다. A 나라의 공격에 대항하여 아이기스 군사 기지에서는 무수히 쏟아지는 폭격 미사일들을 요격하려고 합니다. 이곳에는 백발백중을 자랑하는 요격 시스템이 있지만 운용 비용이 상당하기 때문에 미사일을 최소로 사용해서 모든 폭격 미사일을 요격하려 합니다. A 나라와 B 나라가 싸우고 있는 이 세계는 2 차원 공간으로 이루어져 있습니다. A 나라가 발사한 폭격 미사일은 x 축에 평행한 직선 형태의 모양이며 개구간을 나타내는 정수 쌍 (s, e) 형태로 표현됩니다. B 나라는 특정 x 좌표에서 y 축에 수평이 되도록 미사일을 발사하며, 발사된 미사일은 해당 x 좌표에 걸쳐있는 모든 폭격 미사일을 관통하여 한 번에 요격할 수 있습니다. 단, 개구간 (s, e)로 표현되는 폭격 미사일은 s와 e에서 발사하는 요격 미사일로는 요격할 수 없습니다. 요격 미사일은 실수인 x 좌표에서도 발사할 수 있습니다. 각 폭격 미사일의 x 좌표 범위 목록 targets이 매개변수로 주어질 때, 모든 폭격 미사일을 요격하기 위해 필요한 요격 미사일 수의 최솟값을 return 하도록 solution 함수를 완성해 주세요.

풀이

function solution(targets) {
    targets.sort((a, b) => a[1] - b[1]);

    let result = 0;
    let lastShootPos = -1;

    for (const target of targets) {
        const [startPos, endPos] = target;

        if (lastShootPos < startPos) {
            lastShootPos = endPos - 1;
            result += 1;
        }
    }

    return result;
}

결과