[NodeJs] N과 M (1) (백준 15649번 자바스크립트 노드JS JavaScript)

문제

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

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

입력

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

출력

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

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

예제 입력 1

3 1

예제 출력 1

1
2
3

예제 입력 2

4 2

예제 출력 2

1 2
1 3
1 4
2 1
2 3
2 4
3 1
3 2
3 4
4 1
4 2
4 3

예제 입력 3

4 4

예제 출력 3

1 2 3 4
1 2 4 3
1 3 2 4
1 3 4 2
1 4 2 3
1 4 3 2
2 1 3 4
2 1 4 3
2 3 1 4
2 3 4 1
2 4 1 3
2 4 3 1
3 1 2 4
3 1 4 2
3 2 1 4
3 2 4 1
3 4 1 2
3 4 2 1
4 1 2 3
4 1 3 2
4 2 1 3
4 2 3 1
4 3 1 2
4 3 2 1

 

---

 

 

항상 느끼는 거지만 노드JS로 백준 문제 푸는건 정말 고통스럽습니다.

기본 백트래킹, 순열 문제입니다. Python으로 한 번 해결했었고, 이번엔 자바스크립트로 해결해봤습니다.

 

 

 

Python풀이와 다른 부분은 결과를 출력하는 부분입니다.

아직 nodeJs에 익숙하지 않아서, 다른 사람의 풀이를 보면서 메소드 활용에 대해서 공부하고 있는데

console.log를 많이 사용할 수록 성능이 저하되고, 시간복잡도가 증가한다고 합니다.

그래서 console.log를 최소한으로 하는 출력을 권장하고 있길래 저도 시도해봤습니다.

 

 

 

result를 let선언한 뒤, 여기에 문자열 리터럴을 추가하는 방식의 출력입니다.

이때, '\n' 개행 문자를 추가하여 출력시에 줄바꿈이 되도록 합니다.

출력 console.log 부분에서 trim()을 사용해서 공백과 개행을 전부 제거합니다.

 

 

 

전체 코드

//백준 15649 n과m1

const fs = require('fs');
const input = fs.readFileSync('/dev/stdin').toString().trim().split(' ').map(nm => parseInt(nm));

// const input = require('fs').readFileSync('input.txt').toString().trim().split(' ');
// const [n, m] = [4, 4]
const n = input.shift();
const m = input.shift();

let result = '';

const visited = new Array(10).fill(false);
const arr = [];

function dfs(k) {
    if (k===m) {
        result += `${arr.join(' ')}\n`;
        return;
    }
    for (let i=1; i<n+1; i++) {
        if (visited[i]===true) continue;
        visited[i] = true;
        arr.push(i);
        dfs(k+1);
        arr.pop();
        visited[i] = false;
    }
}

dfs(0);

console.log(result.trim())