[백준 | JavaScript] N과 M(2) (15650)

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

[ 문제 ]

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

• 1부터 N까지 자연수 중에서 중복 없이 M개를 고른 수열

• 고른 수열은 오름차순이어야 한다.

[ 입력 ]

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

[ 출력 ]

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

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

[ 코드 ]

*조합(Combination)
서로 다른 n개 중에 r를 선택하는 경우의 수(순서 無)

const fs = require('fs');
const input = fs.readFileSync('test.txt').toString().trim().split(' ');
const n = parseInt(input[0]);
const m = parseInt (input[1]);

// 풀이
function solution(n, m) {
  let temp = [];
  let answer = "";

  function dfs(idx, start) {	// start 지정
    if (idx === m) {
        const arr = [];
        for (let i = 0; i < m; i++) {
            arr.push(temp[i]);
        }
        answer += `${arr.join(' ')}\n`;
        return;
    }
    for (let i = start; i <= n; i++) {
        temp[idx] = i;
        dfs(idx + 1, i + 1);
    }
  }

  dfs(0, 1); 

  return answer;
}

console.log(solution(n, m));

---

---

[ 멘토링에서 풀이한 코드 ]

const fs = require("fs");
let input = fs.readFileSync("/dev/stdin").toString().trim();
const [n, m] = input.split(' ').map((i) => parseInt(i,10))

const allNum = Array(n).fill().map((v, i) => i+1)
const answer = []

function permutation(currentArr, leftArr) {
    if(currentArr.length === m) {
      // map에 넣을 데이터 정렬
        answer.push(currentArr.sort())
        return;
    }

    leftArr.map((num, i) => {
        permutation([...currentArr, num], [...leftArr.slice(0,i), ...leftArr.slice(i+1)])
    })
}

allNum.map((num, i) => {
    permutation([num], [...allNum.slice(0, i), ...allNum.slice(i+1)])
})

// Set에 담아 중복 제거
function removeDup(arr) {
  return [...new Set(arr.join("|").split("|"))]
    .map((v) => v.split(","))
    .map((v) => v.map((a) => +a));
}

removeDup(answer).forEach((ans) => {
    console.log(ans.join(' '))
})