15655 N과 M (6)

문제

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

•

N개의 자연수 중에서 M개를 고른 수열

•

고른 수열은 오름차순이어야 한다.

입력

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

둘째 줄에 N개의 수가 주어진다. 입력으로 주어지는 수는 10,000보다 작거나 같은 자연수이다.

출력

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

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

예제 입력 1

Plain Text
복사

예제 출력 1

Plain Text
복사

예제 입력 2

Plain Text
복사

예제 출력 2

Plain Text
복사

예제 입력 3

Plain Text
복사

예제 출력 3

Plain Text
복사

My solution

순열을 만들기 위해 정해진 숫자를 이용해야 하는 문제이다.

N개의 자연수 중에서 M개를 고른 수열

조건에 따르면 중복되지 않은 숫자로만 이루어진 수열이 된다.

기존에 숫자는 1부터 N까지 for문으로 반복하면서 값을 넣어줬지만 이제는 배열이 주어지므로 기존에 사용하던 숫자를 인덱스로 취급하는 방법이 있다고 생각했다.

배열의 인덱스이기 때문에 (0 ~ 배열의 마지막 인덱스)까지 1씩 증가하는 방식으로 반복한다.

const DFS = () => {
	...
	for (let i = 0; i < N; i++) {
    if (!perm.includes(sortedElements[i])) {
      perm.push(sortedElements[i]);
      DFS();
      perm.pop();
    }
  }
}
JavaScript
복사

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

수열은 사전순으로 증가해야하기 때문에 주어진 숫자들은 정렬이 필요하다.

const sortedElements = elements.sort((a, b) => a - b);
const DFS = () => {
	...
JavaScript
복사

고른 수열은 오름차순이어야 한다.

위의 조건에 따라 for문 내에서 perm 배열이 비어있지 않을 때 배열의 마지막 원소보다 큰 값을 넣도록 한다.

const DFS = () => {
	...
	for (let i = 0; i < N; i++) {
    if (
      !perm.includes(sortedElements[i]) &&
      (perm.length === 0 || perm[perm.length - 1] < sortedElements[i])
    ) {
      perm.push(sortedElements[i]);
      DFS();
      perm.pop();
    }
  }
}
JavaScript
복사

Code

const solution = function (i) {
  const [[N, M], elements] = i
    .toString()
    .trim()
    .split('\n')
    .map(input => input.split(' ').map(Number));
  const result = [];
  const perm = [];

  const sortedElements = elements.sort((a, b) => a - b);
  const DFS = () => {
    if (perm.length === M) {
      result.push(perm.join(' '));
      return;
    }
    for (let i = 0; i < N; i++) {
      if (
        !perm.includes(sortedElements[i]) &&
        (perm.length === 0 || perm[perm.length - 1] < sortedElements[i])
      ) {
        perm.push(sortedElements[i]);
        DFS();
        perm.pop();
      }
    }
  };

  DFS();
  // BOJ 제출
  console.log(result.join('\n'));
  return result.join('\n');
};

test('TC1', () => {
  expect(
    solution(`3 1
4 5 2`)
  ).toStrictEqual(`2
4
5`);
});
test('TC2', () => {
  expect(
    solution(`4 2
9 8 7 1`)
  ).toStrictEqual(`1 7
1 8
1 9
7 8
7 9
8 9`);
});
test('TC3', () => {
  expect(
    solution(`4 4
1231 1232 1233 1234`)
  ).toStrictEqual(`1231 1232 1233 1234`);
});
JavaScript
복사