15649 N과 M (1)

문제

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

•

1부터 N까지 자연수 중에서 중복 없이 M개를 고른 수열

입력

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

출력

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

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

예제 입력 1

Plain Text
복사

예제 출력 1

Plain Text
복사

예제 입력 2

Plain Text
복사

예제 출력 2

Plain Text
복사

예제 입력 3

Plain Text
복사

예제 출력 3

Plain Text
복사

My solution

재귀를 이용해서 배열에 1씩 증가하는 i를 넣으면 사전순으로 증가하는 순열을 만들 수 있다.

배열의 길이가 M이 되면 그만큼의 숫자를 선택한 것이므로 이때마다 answer 배열에 포함시킨다.

이때 순열을 위해서는 중복된 숫자가 재사용되지 않도록 visited 배열로 체크하는 것이 필요하다.

1부터 N까지의 자연수에서 M개를 선택하는 것이므로 순열에 같은 자연수가 다시 나올 일은 없기 때문이다.

for문을 돌면서 숫자를 전달하게 되면 매번 재귀호출마다 i가 1부터 전달되기 때문에 기존에 1을 배열에 넣었더라도 다시 1을 넣는 경우가 생긴다. 이로 인해 아래와 같은 순열이 나온다.

const permutation = () => {
    if (perm.length === M) {
      answer += perm.join(' ') + '\n';
      return;
    }

    for (let i = 1; i <= N; i++) {
      // if (!visited[i]) {
      //   visited[i] = true;
      perm.push(i);
      permutation(i);
      perm.pop();
      //   visited[i] = false;
      // }
    }
  };
JavaScript
복사

중복을 체크하면 아래와 같이 사전순으로 중복 없는 순열이 출력된다.

const permutation = () => {
    if (perm.length === M) {
      answer += perm.join(' ') + '\n';
      return;
    }

    for (let i = 1; i <= N; i++) {
      if (!visited[i]) {
        visited[i] = true;
        perm.push(i);
        permutation(i);
        perm.pop();
        visited[i] = false;
      }
    }
  };
JavaScript
복사

Code

// sol1. DFS
const solution = function (i) {
  const [N, M] = i.toString().trim().split(' ').map(Number);
  const perm = [];
  const visited = Array(N).fill(false);
  let answer = '';

  const permutation = () => {
    if (perm.length === M) {
      answer += perm.join(' ') + '\n';
      return;
    }

    for (let i = 1; i <= N; i++) {
      if (!visited[i]) {
        visited[i] = true;
        perm.push(i);
        permutation(i);
        perm.pop();
        visited[i] = false;
      }
    }
  };

  permutation(0);
  console.log(answer);
  return answer;
};

test('TC1', () => {
  expect(solution(`3 1`)).toStrictEqual(`1
2
3
`);
});
test('TC2', () => {
  expect(solution(`4 2`)).toStrictEqual(`1 2
1 3
1 4
2 1
2 3
2 4
3 1
3 2
3 4
4 1
4 2
4 3
`);
});
test('TC3', () => {
  expect(solution(`4 4`)).toStrictEqual(`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
`);
});
JavaScript
복사