[BOJ / Node.js] 15663. N과 M(9)

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

15663번: N과 M (9)

문제

N개의 자연수와 자연수 M이 주어졌을 때, 아래 조건을 만족하는 길이가 M인 수열을 모두 구하는 프로그램을 작성하시오.

• N개의 자연수 중에서 M개를 고른 수열

입력

첫째 줄에 N과 M이 주어진다. (1 ≤ M ≤ N ≤ 8)

둘째 줄에 N개의 수가 주어진다. 입력으로 주어지는 수는 10,000보다 작거나 같은 자연수이다.

출력

한 줄에 하나씩 문제의 조건을 만족하는 수열을 출력한다. 중복되는 수열을 여러 번 출력하면 안되며, 각 수열은 공백으로 구분해서 출력해야 한다.

수열은 사전 순으로 증가하는 순서로 출력해야 한다.

예제 입력 1

3 1
4 4 2

예제 출력 1

2
4

 

 

 

Solve

• 주어진 배열 내에서 중복을 체크해줘야하기 때문에 숫자의 갯수를 저장할 count라는 객체를 만들어 초기화시켜 주었습니다.
• 백트래킹을 위한 함수(solution)를 작성해주고, 모든 경로를 탐색하며, 길이가 m일 때  return을 해주도록 조건을 작성해 놓았습니다.
• solution함수에 argument로 count 객체를 넘겨주면서, 중복체크가 가능하도록 하였습니다.
• 모두 탐색후에 중복된 값을을 제거해주기 위하여, removeDuplication 함수를 만들어, 적용해 주었습니다.

Problem

• 사전순으로 정답을 출력해야하기 때문에, solution 함수를 돌리기 이전에, 기존에 주어진 배열을 먼저 sort를 해주지 않아서 오답이 나왔었습니다.

 

Code

const [input1, input2] = require("fs")
  .readFileSync("/dev/stdin")
  .toString()
  .trim()
  .split("\n")
  .map((el) => el.trim());

const [n, m] = input1.split(" ").map((el) => +el);
const values = input2.split(" ").map((el) => +el);
values.sort((a, b) => a - b);

const count = {};
const countInit = () => {
  for (let i = 0; i < n; i++) {
    count[values[i]] = 0;
  }
  for (let i = 0; i < n; i++) {
    count[values[i]]++;
  }
};

const answer = [];

const solution = (v, arr, count) => {
  if (arr.length === m) {
    answer.push(arr);
    return;
  }

  count[values[v]] -= 1;

  for (let i = 0; i < n; i++) {
    if (count[values[i]] > 0) solution(i, [...arr, values[i]], { ...count });
  }
};

for (let i = 0; i < n; i++) {
  countInit();
  solution(i, [values[i]], count);
}

const removeDuplication = (arr) => {
  return [...new Set(arr.join("|").split("|"))]
    .map((v) => v.split(","))
    .map((v) => v.map((el) => +el));
};
const arr = removeDuplication(answer);
console.log(arr.map((el) => [...el].join(" ")).join("\n"));