글 읽기 - [Node JS] 틀린 부분을 찾지 못하고 있습니다

hant422 3년 전 0

TC 채점중 한 53퍼정도에서 틀립니다.

DFS를 사용해 낮은 숫자부터 하나씩 넣어보며 해답을 찾는 방법을 사용했습니다.

어느 부분을 놓치고 있는걸까요?

const fs = require("fs");
const input = fs.readFileSync("/dev/stdin", "utf8").trim().split("\n");

const _N = +input[0];
const _X = input[1].split(" ").map((c) => +c);

/**
 * @description 두개의 배열을 정렬하여 병합하는 함수
 * @param {Array} left 병합할 배열
 * @param {Array} right 병합할 배열
 * @returns 정렬되어 병합된 배열
 */
function merge(left, right) {
  let result = [];
  let leftIndex = 0;
  let rightIndex = 0;

  while (leftIndex < left.length && rightIndex < right.length) {
    if (left[leftIndex] < right[rightIndex]) {
      result.push(left[leftIndex]);
      leftIndex++;
    } else {
      result.push(right[rightIndex]);
      rightIndex++;
    }
  }

  return [...result, ...left.slice(leftIndex), ...right.slice(rightIndex)];
}

/**
 * @description 병합 정렬 함수
 * @param {Array} arr 병합 정렬이 필요한 함수
 * @returns 정렬된 함수
 */
function mergeSort(arr) {
  if (arr.length < 2) return arr;

  const mid = Math.floor(arr.length / 2);
  const left = arr.slice(0, mid);
  const right = arr.slice(mid);

  return merge(mergeSort(left), mergeSort(right));
}

/**
 * @description X를 가지고 arr을 숌 사이 수열로 변환
 * @param {number[]} X X에 들어가는 수
 * @param {boolean[]} used X에 사용한 수
 * @param {number[]} ans 숌 사이 수열로 변할 배열
 * @param {number} index 현재 index
 * @returns {boolean} 변환 성공 여부
 */
function dfs(X, used, ans, index) {
  if (index === -1) return true;

  for (let i = 0; i < X.length; i += 1) {
    if (!used[i] && ans[index + X[i] + 1] === -1) {
      used[i] = true;
      ans[index] = X[i];
      ans[index + X[i] + 1] = X[i];

      if (dfs(X, used, ans, ans.indexOf(-1, index + 1))) return true;

      used[i] = false;
      ans[index] = -1;
      ans[index + X[i] + 1] = -1;
    }
  }

  return false;
}

/**
 * @description 함수 집합 X가 주어졌을 때, 숌 사이 수열 S를 출력하는 함수
 * @param {number} N X의 크기
 * @param {number[]} X X에 들어가는 수
 * @returns {string} 숌 사이 수열
 */
function solution(N, X) {
  const sortedX = mergeSort(X);
  const used = Array(N).fill(false);
  const ans = Array(N * 2).fill(-1);
  return dfs(sortedX, used, ans, 0) ? ans.join(" ") : "-1";
}

console.log(solution(_N, _X));

댓글을 작성하려면 로그인해야 합니다.

문제

문제

출처

ICPC

[Node JS] 틀린 부분을 찾지 못하고 있습니다

hant422 3년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말