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

Adela·2020년 6월 26일
1

백준온라인저지

목록 보기
9/53
post-thumbnail

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의 원소들을 출력한다.

백트래킹 알고리즘 연습으로 해보았다.
입문용이라고 되어있어서 풀었는데, 재귀를 익히고 기초를 닦기 좋은 것 같다.

알고리즘 공부도 할 겸 조만간 알고리즘 정리를 해야겠다. 네이버 블로그에 할지 여기에 할지 모르겠지만...

profile
개발 공부하는 심리학도

0개의 댓글