문제
10이하의 N개의 자연수가 주어지면 이 중 M개를 뽑아 일렬로 나열하는 방법을 모두 출력합 니다.
[입력설명]
첫 번째 줄에 자연수 N(3<=N<=10)과 M(2<=M<=N) 이 주어집니다. 두 번째 줄에 N개의 자연수가 오름차순으로 주어집니다.
[출력설명]
첫 번째 줄에 결과를 출력합니다. 맨 마지막 총 경우의 수를 출력합니다. 출력순서는 사전순으로 오름차순으로 출력합니다.
입력예제 1
3 2
3 6 9
출력예제 1
3 6
3 9
6 3
6 9
9 3
9 6
6
문제 풀이
코드
- 사전순으로 오름차순으로 출력하라고 되어있는데, 전위순회를하는 DFS에서는 기본적인 문제풀이를 하면 오름차순으로 정렬된다. (단 문제와 같이 미리 정렬되어있는 경우에서)
- 중복순열이 아니기때문에 사용했는지 체크하는 배열 ch를 만들어서, 중복을 방지한다.
- 경우의 수는 3 x 2 = 6개이다.
- 문제풀이 원리는 다음과 같다
<html>
<head>
<meta charset="UTF-8">
<title>출력결과</title>
</head>
<body>
<script>
function solution(m, arr){
let answer=[];
n=arr.length;
let ch=Array.from({length:n}, ()=>0); //사용했는지 체크하는 배열(중복 방지!)
let tmp=Array.from({length:m}, ()=>0); //뽑은것 넣는 배열
function DFS(L){
if(L===m){
answer.push(tmp.slice()); //깊은복사
}
else{
for(let i=0; i<n; i++){
//ch[i]가 0일때(중복되지 않을 때) 사용 가능
if(ch[i]===0){
ch[i]=1; //사용하면 1으로 바꿈
tmp[L]=arr[i];
DFS(L+1);
ch[i]=0; //백해서 다시 돌아오는 지점에서는 0으로 초기화시켜줌
}
}
}
}
DFS(0);
return answer;
}
let arr=[3, 6, 9];
console.log(solution(2, arr));
</script>
</body>
</html>
<!--
<html>
<head>
<meta charset="UTF-8">
<title>출력결과</title>
</head>
<body>
<script>
function solution(m, arr){
let answer=[];
n=arr.length;
let ch=Array.from({length:n}, ()=>0);
let tmp=[];
function DFS(L){
if(L===m){
answer.push(tmp.slice());
}
else{
for(let i=0; i<n; i++){
if(ch[i]===0){
ch[i]=1;
tmp.push(arr[i]);
DFS(L+1);
ch[i]=0;
tmp.pop();
}
}
}
}
DFS(0);
return answer;
}
let arr=[3, 6, 9];
console.log(solution(2, arr));
</script>
</body>
</html>
-->
내가 짱이다 😎 매일 조금씩 성장하기🌱
9/17
백하면서 반드시 체크배열 풀어줄 것!
ch[i]=0;