[백준 | JavaScript] N과 M (15649)

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

[ 문제 ]

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

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

[ 입력 ]

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

[ 출력 ]

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

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

[ 코드 ]

*순열(Permutation)
서로 다른 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 = "";
  let visited = [];

  function dfs(idx) {
    if (idx === m) {	
        const arr = [];
        for (let i = 0; i < m; i++) {
            arr.push(temp[i]);
        }
        return answer += `${arr.join(' ')}\n`;	// 수열 추가
    }
    for (let i = 1; i <= n; i++) {
        if (!visited[i]) {
            temp[idx] = i;
            visited[i] = true;
            dfs(idx + 1);	// 인덱스 증가 재귀
            visited[i] = false;
        }
    }
  }

  dfs(0); 	// 인덱스 0부터 시작

  return answer;
}

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

---

백트래킹을 사용하는 문제... 어렵다.... 아래 강의의 도움을 받았다.
https://youtu.be/Enz2csssTCs?si=jzX5D_t5uhwRT-1E

---

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

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) {
        answer.push(currentArr)
        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)])
})


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