문제
1부터 N까지 번호가 적힌 구슬이 있습니다. 이 중 중복을 허락하여 M번을 뽑아 일렬로 나열 하는 방법을 모두 출력합니다.
[입력설명]
첫 번째 줄에 자연수 N(3<=N<=10)과 M(2<=M<=N) 이 주어집니다.
[출력설명]
첫 번째 줄에 결과를 출력합니다. 맨 마지막 총 경우의 수를 출력합니다. 출력순서는 사전순으로 오름차순으로 출력합니다.
입력예제 1
3 2
출력예제 1
1 1
1 2
1 3
2 1
2 2
2 3
3 1
3 2
3 3
9
문제 풀이
예습이론
- 중복순열이란, 순서대로 나열하는데 중복을 허용하는 것이다.또한 순열이란 순서를 중요하게 생각하기 때문에 {1, 2}와 {2, 1}을 다르게 생각한다.(조합은 같은것으로 침)
- DFS 사용의 효용성
- 얕은복사한 것(tmp)을 push하면, 이미 push한 것이라도 나중 tmp값을 변경한다면 push한 값도 변한다. 따라서, 반드시 slice()메소드를 통해 깊은 복사해준다.
코드
- 문제 풀이 원리는 다음과 같다.
<html>
<head>
<meta charset="UTF-8">
<title>출력결과</title>
</head>
<body>
<script>
function solution(n, m){
let answer=[];
let tmp=Array.from({length:m}, ()=>0); //길이가 m인 배열 0으로 초기화해서 생성
function DFS(L){
if(L===m){
answer.push(tmp.slice()); //slice는 깊은복사(깊은복사 안하면 마지막갚으로 모두 push됨)
}
else{
for(let i=1; i<=n; i++){
tmp[L]=i; //넣고
DFS(L+1); //다음 레벨로 넘어감
}
}
}
DFS(0);
return answer;
}
console.log(solution(3, 2));
</script>
</body>
</html>
내가 짱이다 😎 매일 조금씩 성장하기🌱
9/17
새로운 배열 생성 및 사용