[백준] N과 M(2) / JavaScript / node.js

문제

---

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

15650번: N과 M (2)

 

코드

---

//실버3 N과 M(2)
//https://www.acmicpc.net/problem/15650
const fs = require("fs");
const filePath = process.platform === "linux" ? "/dev/stdin" : "./input.txt";
let input = fs.readFileSync(filePath).toString().trim().split("\r\n");
 
function getPermutation(arr, selectNumber) {
  const result = []; //결과를 담을 배열
  if (selectNumber === 1) {
    return arr.map((value) => [value]); //1개 선택은 모든 원소를 그대로 return
  }
 
  arr.forEach((fixed, index, origin) => {
    const rest = [...origin.slice(index + 1)]; //해당하는 fixed를 제외한 나머지 배열
    const permutations = getPermutation(rest, selectNumber - 1); //나머지에 대한 순열을 구하기
    const attached = permutations.map((permutation) => [fixed, ...permutation]); //돌아온 순열에 떼 놓은 fixed값 붙이기
 
    result.push(...attached);
  });
 
  return result;
}
 
const N = Number(input[0].split(" ")[0]);
const M = Number(input[0].split(" ")[1]);
const numbers = [];
for (let i = 1; i <= N; i++) numbers.push(i); //1부터 N까지의 수를 담은 배열
const result = getPermutation(numbers, M); //numbers와 M으로 순열함수 호출
//result의 각 순열 결과에 대해 한 칸 띄워 출력하기
for (let i = 0; i < result.length; i++) {
  console.log(result[i].join(" "));
}

 

후기

---

• N과 M(1)번 문제에 오름차순인 수열만 출력해야하는 조건이 하나 더 붙었다. 그래서 (1)번문제와 달리 이 문제는 조합을 이용하여 풀었다. 순열 말고 조합을 이용하면 중복 값을 제거해주므로 자동으로 오름차순된 수열만 return하는 특징이 있다 

  ---

잘못된 내용이나 수정이 필요한 내용이 있으면 언제든 댓글 달아주세요 감사합니다 😀