[알고리즘] 백준 15655 - N과 M
https://www.acmicpc.net/problem/15655
문제설명
N개의 자연수와 자연수 M이 주어졌을 때, 아래 조건을 만족하는 길이가 M인 수열을 모두 구하는 프로그램을 작성하시오. N개의 자연수는 모두 다른 수이다.
- N개의 자연수 중에서 M개를 고른 수열
- 고른 수열은 오름차순이어야 한다.
풀이방법
- permutation함수는 n과 m, arr를 인수로 전달받는다.
- result 배열에는 길이가 m인 수열이 저장된다.
- 그리고 isSelected는 길이가 n이고, false로 초기화되어 있다.
각 수열에는 중복된 값이 들어가면 안되기때문에 isSelected배열을 방문체크배열로 사용할 것이다. - 수열은 오름차순이여야 하기때문에 우선 arr배열을 오름차순으로 정렬해 준다.
- findPermutation함수
- 매개변수로 arr의 index를 의미하는 cur와, 재귀함수를 호출하며 생성할 수열의 정보를 담을 numArr를 전달한다.
- cur이 m과 같아지면 result배열에 현재까지 생성한 수열을 넣어준다.
여기서 주의할점!result.push(numArr)
이렇게 해주면 numArr의 주소값이 result에 들어가서 findPermutation이 종료되고 난 후엔 result에 들어간 모든 수열이 같은 값을 출력한다!!!!!
그래서 ★spread연산자를 사용해 numArr의 값과 똑같은 값을 가지는 새로운 배열을 만들어 result에 넣어준다.★
- for문을 보면 만약 해당 호출의 numArr를 구성할때 isSelected내의 값들을 검사해서 이미 사용된 값이면 continue를 사용해 다음index를 검사한다.
그리고numArr[cur] = arr[i];
이 부분이 수열에 값을 넣는부분인데, 배열의 cur번째값으로 arr의 i번째 값을 넣는다. 이부분을 잘 이해해야한다!!!! 재귀함수가 호출되는 순서를 적어봤는데, for문내의 i와 잘 연결해서 추론해보면 이해가 될것이다..!
function permutation(n, m, arr) {
const result = [];
const isSelected = Array.from(n).fill(false);
arr.sort((a, b) => a - b);
function findPermutation(cur, numArr) {
if (cur === m) {
result.push([...numArr]);
return;
}
for (let i = 0; i < n; i++) {
if (isSelected[i]) {
continue;
}
isSelected[i] = true;
numArr[cur] = arr[i];
findPermutation(cur + 1, numArr);
isSelected[i] = false;
}
}
findPermutation(0, []);
console.log(result);
}
permutation(4, 2, [4, 5, 2, 9]);
Author And Source
이 문제에 관하여([알고리즘] 백준 15655 - N과 M), 우리는 이곳에서 더 많은 자료를 발견하고 링크를 클릭하여 보았다 https://velog.io/@dolarge/알고리즘-백준-15655-N과-M저자 귀속: 원작자 정보가 원작자 URL에 포함되어 있으며 저작권은 원작자 소유입니다.
우수한 개발자 콘텐츠 발견에 전념 (Collection and Share based on the CC Protocol.)