N과 M(1)
문제
자연수 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출처
- 문제를 만든 사람: baekjoon
해결한 코드
function b15649() {
var fs = require('fs');
var input = fs.readFileSync('/dev/stdin').toString().split('\n');
// var input = fs.readFileSync(__dirname + '/stdin.txt').toString().replace(/\r/g, "").split(' ');
var n = parseInt(input[0])
var m = parseInt(input[1])
var temp = new Array(n).fill(0)
for (var i = 1; i <= n; i++) {
temp[i - 1] = i
}
var ans = []
for (var p = 0; p < temp.length; p++) {
permutation(ans, temp[p], temp, m, temp[p].toString())
}
print(ans)
}
function permutation(ans, current, temp, m, str) {
var array = str.split(' ')
if (array.length == m) {
ans.push(str)
return ans
} else {
var newArr = temp.slice()
var index = newArr.findIndex(e => e === current)
newArr.splice(index, 1)
for (var i = 0; i < newArr.length; i++) {
permutation(ans, newArr[i], newArr, m, str + " " + newArr[i])
}
}
}
function print(ans){
for(var i=0; i<ans.length; i++){
console.log(ans[i])
}
}
b15649()알고리즘
1. 1부터 n까지의 숫자가 들어있는 배열 temp를 만든다.
1-1. if (n=4) -> temp = [ 1, 2, 3, 4 ]
2. temp안의 숫자들의 순열을 구한다.
2-1. 순열을 구하기 위해 필요한 변수들은?
👉🏻 순열을 시작하는 원소, 순열을 돌릴 원소들이 포함된 배열, m(각 결과값 크기), 순열 결과값들
2-2. ex. temp = [ 1, 2, 3, 4 ] 에서 1부터 시작하면
1 뒤에 붙을 수 있는 숫자 => 2,3,4
∴ 1 뒤에 붙을 숫자들의 배열 = [ 2, 3, 4 ]을 만들어 주기 위해temp.splice('1의 인덱스', 1)
※ temp를 그냥 slice해버리면 안됨. 다음 temp를 써야할 때 temp가 비어버리기 때문
2-3.var newArr = temp.slice()로 temp를 복제한 임시배열 newArr를 만듦
2-4.newArr.splice('1의 인덱스', 1)을 해줌
2-5. 순열로 만들어진 숫자는 공백을 포함한 문자열로(str + " " newArr[i].toString())만듦
2-6. 순열로 만들어진 숫자의 갯수가 m과 일치하면
👉🏻 답을 어디에 저장해놓아야 할텐데...
앗 ! 순열 함수에 답 모아둘 배열도 필요했다 !
따라서 순열 함수에 답 모아둘 배열도 만들어주고 (코드에서는ans가 바로 이에 해당 ), str에 있는 숫자들의 갯수가 m과 일치하면 ans에 push.
👉🏻 str를 공백 기준으로 split하여 나온 배열의 length 가 m과 일치하면 ans에 push.
2-7. 함수를 종료(return)3. ans의 원소들을 출력한다.
백트래킹 알고리즘 연습으로 해보았다.
입문용이라고 되어있어서 풀었는데, 재귀를 익히고 기초를 닦기 좋은 것 같다.
알고리즘 공부도 할 겸 조만간 알고리즘 정리를 해야겠다. 네이버 블로그에 할지 여기에 할지 모르겠지만...
