[코딩테스트]백준 - N과 M(4)

N과 M(4)

문제

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

• 1부터 N까지 자연수 중에서 M개를 고른 수열
• 같은 수를 여러 번 골라도 된다.
• 고른 수열은 비내림차순이어야 한다.
• 길이가 K인 수열 A가 A1 ≤ A2 ≤ ... ≤ AK-1 ≤ AK를 만족하면, 비내림차순이라고 한다.

입력

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

출력

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

예제 입력 1

3 1

예제 출력 1

1
2
3

예제 입력 2

4 2

예제 출력 2

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

예제 입력 3

3 3

예제 출력 3

1 1 1
1 1 2
1 1 3
1 2 2
1 2 3
1 3 3
2 2 2
2 2 3
2 3 3
3 3 3

출처

• 문제를 만든 사람: baekjoon

해결한 코드

function b15652(){
    var fs = require('fs');
    var input = fs.readFileSync('/dev/stdin').toString().split(' ');
    // 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 j=0; j<temp.length; j++){
        select(ans, temp[j], temp, temp[j].toString(), m)
    }
    var answer = ''
    for(var a=0; a<ans.length; a++){
        answer += `${ans[a]}\n`
    }
    console.log(answer)
}

function select(ans, current, temp, str, m){
    var index = temp.findIndex(e=> e===current)
    var newArr = temp.slice(index, temp.length)
    var array = str.split(' ')
    if(array.length == m){
        ans.push(str)
        return 
    }
    for(var i=0; i<newArr.length; i++){
        select(ans, newArr[i], newArr, str+" "+newArr[i].toString(), m)
    }
}

b15652()

알고리즘

• N과 M(1), N과 M(2), N과 M(3)

조합 결과 값이 비내림차순되어 있어야 하므로 temp 배열을 만들어 주었다.

1. 만약 temp = [ 1, 2, 3, 4 ], m=4 라면
   1-1. 1 뒤에 올 수 있는 수는 [ 2, 3, 4 ]
   1-2. 2 뒤에 올 수 있는 수는 [ 3, 4 ]
   1-3. 3 뒤에 올 수 있는 수는 [ 4 ]
2. 조합으로 붙일 수 있는 수의 범위를 temp.slice('현재 조합된 수의 다음 인덱스', 끝) 해주면서 수를 조합한다.
   2-1. 조합 함수에 들어갈 변수?
   👉🏻 temp, 조합 시작하는 temp원소, 조합한 값(str), m, 조합한 값을 저장할 ans
   2-2. newArr라는 temp를 slice한 배열을 만들어 줌
   => 이게 1번에서 [ 2, 3, 4 ] ... [ 3, 4 ] ... [ 4 ] ... 가 됨
   2-3. str에 현재 원소를 붙여 조합 값을 만듦(사이에 공백 붙임)
   2-4. str에 공백이 아닌 숫자들의 갯수가 m이랑 같으면 ans에 저장한 후 함수 종료(return)
3. ans의 원소들을 빈 문자열 answer에 줄바꿈하며 붙임
   => 하나의 문자열로 만들어 console.log()를 한번만 호출하기 위함 (N과 M(3) 참고)
4. answer를 출력