[백준 15654] N과 M (5) with Node.js

문제 링크

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

15654번: N과 M (5)

풀이

const solve = (N, M, arr) => {
	let permutation = [];
	const chosen = new Array(N).fill(false);
	const output = [];
	const recursion = () => {
		if (permutation.length === M) {
			output.push(permutation.join(' '));
		} else {
			chosen.forEach((bool, i) => {
				if (!bool) {
					chosen[i] = true;
					permutation.push(arr[i]);
					recursion();
					chosen[i] = false;
					permutation.pop();
				}
			});
		}
	};

	recursion();
	console.log(output.join('\n'));
};

const [N, M, ...arr] = require('fs').readFileSync('/dev/stdin').toString().trim().split(/\s+/).map(v => +v);
arr.sort((a, b) => a - b);
solve(N, M, arr);

먼저 주어진 수들을 오름차순으로 정렬한다.

 

정렬된 수들을 하나씩 순회하면서 현재 선택 여부를 chosen 배열에 true로 표시한다.

하나의 수를 선택하면 재귀적으로 다시 순회하면서 아직 선택되지 않은(chosen의 해당 인덱스의 값이 false) 수를 계속 선택한다.

선택된 수들이 M개가 되면 더 이상 수를 선택하지 않고 output에 지금까지 선택된 수들을 문자열로 저장한다.

재귀호출에서 빠져나오면서 재귀호출 직전에 선택되었던 수를 선택해제 한다. (chosen의 해당 인덱스의 값을 다시 false로 되돌린다.)

recursion()이 끝나면 지금까지 output에 저장한 수열을 출력한다.

 

이렇게 하면 M 개의 수로 이루어진 중복되지 않는 수열을 오름차순으로 출력할 수 있다.