[백준/Node.js] 15650번: N과 M(2)

목차

📝 문제

🎯 알고리즘 핵심 단계

✅ 실습 인증 파트_코드

⚡ 트러블 슈팅

🤔 이것도 한 번 생각해봐요! (참고 자료)

---

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

 

📝 문제

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

• 1부터 N까지 자연수 중에서 중복 없이 M개를 고른 수열
• 고른 수열은 오름차순이어야 한다.

입력

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

 

출력

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

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

---

🎯 알고리즘

💡 문제 이해

    1부터 n까지의 숫자 중에서 중복 없이 m개를 선택하는 모든 경우의 수(조합) 를 오름차순으로 출력하는 문제

 

💡 문제 접근

    DFS 기법으로 모든 조합을 찾는 것이 포인트

 

---

✅ 실습 인증 _코드

const fs = require('fs');
const [n, m] = fs.readFileSync('/dev/stdin').toString().trim().split(' ').map(Number);


let answer = [];

function dfs(depth, start, arr){
    if(depth == m) {
        answer.push([...arr]);
        return;
    }else{
        for (let i = start; i <= n; i++) {
            dfs(depth+1, i+1, [...arr, i]  )

        }
    }

}
dfs(0,1,[]);
console.log(answer.map(arr => arr.join(" ")).join("\n"));

 

---

⚡ 트러블 슈팅

       🌱 console.log(answer.map(arr => arr.join(" ")).join("\n"))

               =>  console.log(answer.join("\n")); 이렇게 출력하면 안됨!

 

               -   arr.join(' '):    각 조합 배열을 공백으로 구분된 문자열로 변환 (예: [1, 2] → "1 2")

               -  .map(...):       모든 조합 배열에 대해 위 작업을 수행

               -   join('\n'):       변환된 문자열들을 줄바꿈(\n)으로 이어 붙임

---

🤔 이것도 한 번 생각해봐요! (참고 자료)