문제
자연수 N과 M이 주어졌을 때, 아래 조건을 만족하는 길이가 M인 수열을 모두 구하는 프로그램을 작성하시오.
•
1부터 N까지 자연수 중에서 중복 없이 M개를 고른 수열
•
고른 수열은 오름차순이어야 한다.
입력
첫째 줄에 자연수 N과 M이 주어진다. (1 ≤ M ≤ N ≤ 8)
출력
한 줄에 하나씩 문제의 조건을 만족하는 수열을 출력한다. 중복되는 수열을 여러 번 출력하면 안되며, 각 수열은 공백으로 구분해서 출력해야 한다.
수열은 사전 순으로 증가하는 순서로 출력해야 한다.
예제 입력 1
3 1
Plain Text
복사
예제 출력 1
1
2
3
Plain Text
복사
예제 입력 2
4 2
Plain Text
복사
예제 출력 2
1 2
1 3
1 4
2 3
2 4
3 4
Plain Text
복사
예제 입력 3
4 4
Plain Text
복사
예제 출력 3
1 2 3 4
Plain Text
복사
My solution
N과 M (1) 문제를 보면 만든 수열을 구성하는 숫자가 아래와 같이 중복만 존재하지 않았다.
(N : 4, M : 2) 일 때
우선 위와 같이 중복만 존재하지 않는 수열을 만들기 위해 아래의 코드를 먼저 작성했다.
jest에서 result에 “2 1”, “3 1”, “3 2”,,, 등이 없어야 한다고 말해준다.
const DFS = () => {
if (perm.length === M) {
result.push(perm.join(' '));
return;
}
for (let i = 1; i <= N; i++) {
if (!perm.includes(i)) {
perm.push(i);
DFS();
perm.pop();
}
}
};
JavaScript
복사
이 문제에서는 추가 조건이 있다.
고른 수열은 오름차순이어야 한다.
따라서 하나의 조건을 더 추가해본다.
한 라인마다 넣어줄 perm의 배열에 어떤 요소를 push하기 전에
기존에 있던 perm[perm.length-1]보다 더 큰 숫자가 들어올 때만 push하도록 허용하는 것이다.
const DFS = () => {
if (perm.length === M) {
result.push(perm.join(' '));
return;
}
for (let i = 1; i <= N; i++) {
if (
!perm.includes(i) &&
(perm.length === 0 || perm[perm.length - 1] < i)
) {
perm.push(i);
DFS();
perm.pop();
}
}
};
JavaScript
복사
비교할 인덱스를 perm.length-1로 두는 이유는 처음에는 하나의 요소, 그 다음부터는 이미 오름차순이므로 맨뒤에 있는 요소를 가리키면 되기 때문이다.
유의할 점은 perm 배열에 아무 요소도 없는 상태에서는 항상 조건을 참으로 하여 어떤 숫자든 push할 수 있지만 요소가 존재한다면 그 때부터는 비교해야한다는 것이다.
스터디원 풀이
temp에 수정이 가해지면 result에 넣은 temp 배열은 다 같은 temp 배열을 참조한다. 따라서 얕은 복사해서 새로운 Array를 만들어주는 방식을 사용해서 불변성을 지켜주면 된다. 아니면 출력을 위해 join(’’)으로 문자열화해서 넣는 방식이 있다.
Code
const solution = function (i) {
const [N, M] = i.toString().trim().split(' ').map(Number);
const result = [];
const perm = [];
const DFS = () => {
if (perm.length === M) {
result.push(perm.join(' '));
return;
}
for (let i = 1; i <= N; i++) {
if (
!perm.includes(i) &&
(perm.length === 0 || perm[perm.length - 1] < i)
) {
perm.push(i);
DFS();
perm.pop();
}
}
};
DFS();
// BOJ 제출
console.log(result.join('\n'));
return result.join('\n');
};
test('TC1', () => {
expect(solution(`3 1`)).toStrictEqual(`1
2
3`);
});
test('TC2', () => {
expect(solution(`4 2`)).toStrictEqual(`1 2
1 3
1 4
2 3
2 4
3 4`);
});
test('TC3', () => {
expect(solution(`4 4`)).toStrictEqual(`1 2 3 4`);
});
JavaScript
복사
