[자바스크립트] 15651 N과 M (3)

15651번: N과 M (3)

문제

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

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

 

 

입력

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

 

 

출력

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

수열은 사전 순으로 증가하는 순서로 출력해야 한다.

 

 

예제 입력 1

4 2

 

 

예제 출력 1

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

 

 

자료구조

① 정수: n, m

② 배열: answer

 

 

알고리즘

① DFS 함수:

    a. `dfs(depth, arr)`: 깊이 우선 탐색을 통해 순열을 생성하는 함수.

    b. `depth`: 현재까지 선택한 순열의 길이.

    c. `arr`: 현재까지 선택한 순열의 요소들을 담은 배열.

② 종료조건 및 정답 처리: `depth`가 목표 길이 `m`에 도달하면 현재까지의 순열을 문자열로 변환하고 `answer` 에 추가한 후 함수 종료.

③ 하부단계(함수) 호출: 1부터 n까지의 수를 순회하면서 각 숫자를 현재 순열에 추가하고, depth를 증가시키며 재귀 호출.

④ 순열 생성: dfs(0, [])로 초기 호출하여 순열 생성을 시작

⑤ 결과 문자열 생성: DFS가 종료되면서 `answer` 변수에 모든 순열 결과가 누적되었음.

 

 

소스 코드 1

const fs = require('fs');

const filePath = process.platform === 'linux' ? '/dev/stdin' : '../../input.txt';
const [n, m] = fs.readFileSync(filePath).toString().trim().split(" ").map(Number);

let answer = []; // 순열 결과 저장 배열

function dfs(depth, arr) {
  // 종료조건 처리 + 정답 처리
  if (depth === m) {
    answer.push([...arr]); // 결과 배열에 현재 순열 추가
    return;
  }

  // 하부단계(함수) 호출
  for (let i = 1; i <= n; i++) {
    dfs(depth + 1, [...arr, i]); // 배열 스프레드 연산자로 새로운 요소 추가
  }
}

dfs(0, []);

for (const element of answer) {
  console.log(...element);
}

시간초과

15649 N과 M (1) 에서 중복 확인 부분을 제외하면 답이 됨. 근데 시간초과도 됨.💁‍♂️💫

 

 

소스 코드 2

const fs = require('fs');
const filePath = process.platform === 'linux' ? '/dev/stdin' : '../../input.txt';
const [n, m] = fs.readFileSync(filePath).toString().trim().split(" ").map(Number);

let answer = ""; // 순열 결과 저장 문자열 변수

function dfs(depth, arr) {
  // 종료조건 처리 + 정답 처리
  if (depth === m) {
    answer += `${arr.join(" ")}\n`; // 현재 순열을 문자열로 변환하여 결과에 추가
    return;
  }

  // 하부단계(함수) 호출
  for (let i = 1; i <= n; i++) {
    dfs(depth + 1, [...arr, i]); // 배열 스프레드 연산자로 새로운 요소 추가
  }
}

dfs(0, []);

console.log(answer);

1008ms

 

소스코드1:

for (const element of answer) {
  console.log(...element);
}

이 코드는 answer 배열을 모두 반복하면서 각 순열을 출력한다.

 

소스코드2:

console.log(answer);

이 코드는 answer 배열 전체를 문자열로 변환하여 출력한다.

 

소스코드2에서는 `arr.join(" ")`을 사용하여 각 순열을 문자열로 변환하여 한 번에 출력하고 있다. 이는 소스코드1의 배열을 모두 반복하면서 출력하는 과정보다 빠를 수 있다.

 

 

소스 코드 3

const fs = require('fs');
const filePath = process.platform === 'linux' ? '/dev/stdin' : '../../input.txt';
const [n, m] = fs.readFileSync(filePath).toString().trim().split(" ").map(Number);

let answer = ""; // 순열 결과 저장 문자열 변수

function dfs(depth, arr) {
  // 종료조건 처리 + 정답 처리
  if (depth === m) {
    answer += `${arr.join(" ")}\n`; // 현재 순열을 문자열로 변환하여 결과에 추가
    return;
  }

  // 하부단계(함수) 호출
  for (let i = 1; i <= n; i++) {
    arr[depth] = i;
    dfs(depth + 1, arr); // 새로운 요소를 추가한 배열로 재귀 호출
  }
}

dfs(0, []);

console.log(answer);

824ms

 

소스코드2:

dfs(depth + 1, [...arr, i]);

배열 복제([...arr, i])를 통해 새로운 배열을 생성하고 전달하고 있다.

소스코드3:

arr[depth] = i;
dfs(depth + 1, arr);

배열 복제 없이 기존 배열에 값을 직접 할당하여 재귀 호출한다. 이렇게 하면 새로운 배열을 생성하는 오버헤드가 줄어들어 성능이 향상될 수 있다.

 

참고

https://www.youtube.com/watch?v=aofZJvWjZIY

 

 

 

✔ 출처

https://www.acmicpc.net/problem/15651