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

N과 M(3)

문제

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

• 1부터 N까지 자연수 중에서 M개를 고른 수열
• 같은 수를 여러 번 골라도 된다.

입력

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

출력

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

예제 입력 1

3 1

예제 출력 1

1
2
3

예제 입력 2

4 2

예제 출력 2

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

예제 입력 3

3 3

예제 출력 3

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

출처

• 문제를 만든 사람: baekjoon

해결한 코드

function b15651() {
    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 ans = []
    for (var s = 1; s <= n; s++) {
        repeatedCom(ans, s.toString(), n, m)
    }
    var answer = ''
    for(var i=0; i<ans.length; i++){
        answer += `${ans[i]}\n`
    }
    console.log(answer)
}

function repeatedCom(ans, str, n, m) {
    var array = str.split(' ')
    if (array.length == m) {
        ans.push(str)
        return
    } else {
        for (var i = 1; i <= n; i++) {
            repeatedCom(ans, str + " " + i.toString(), n, m)
        }
    }
}

b15651()

알고리즘

• 시간초과가 계속 떠서 고민했는데, 자바스크립트에서는 console.log()가 시간을 많이 잡는다고 한다.
• 따라서 답을 한번에 저장한 후 console.log()를 딱 한번만 호출해야 한다.
• N과 M(1), N과 M(2)

1. 같은 수가 여러번 중복되어도 되는 순열 함수를 만들어 푼다.
   중복 순열 함수에 필요한 변수?
   👉🏻 답을 저장할 배열, 각 순열의 결과값인 str, n, m
   ※ 같은 수가 여러번 들어가도 되기에 굳이 temp 배열을 만들 필요가 없다.
   ex. n = 4 라면,
   1 다음에 들어갈 숫자 => 1, 2, 3, 4 => str = '1 1'
   1 1 다음에 들어갈 숫자 => 1, 2, 3, 4 => str = '1 1 1'
   1 1 1 다음에 들어갈 숫자 => 1, 2, 3, 4 => str = '1 1 1 1'
   ...
   2 다음에 들어갈 숫자 => 1, 2, 3, 4 => str = '2 1'
   2 1 다음에 들어갈 숫자 => 1, 2, 3, 4 => str = '2 1 1'
   ...
2. (중복 순열 함수 내에서) 1부터 n만큼 반복문으로 돌며 공백을 붙인 결과값(str)을 만든다.
3. str에서 공백을 제외한 숫자의 길이가 m과 같으면 ans에 저장하고 함수를 종료(return)한다.
4. ans의 원소를 하나의 문자열로 만든다.
   4-1. 빈 문자열 변수 answer에 ans의 원소들을 차례로 붙인다.
   4-2. 이때, 원소마다 줄바꿈(\n)을 해주어야 한다.
5. answer를 출력한다.

console.log()를 반복문 내에, 재귀 내에 붙여서 계속 실패했던 문제.. 🤦🏻‍♀️