[백준 문제풀이] 5568번 카드 놓기 (node.js)

5568 카드 놓기

문제

상근이는 카드 n(4 ≤ n ≤ 10)장을 바닥에 나란히 놓고 놀고있다. 각 카드에는 1이상 99이하의 정수가 적혀져 있다. 상근이는 이 카드 중에서 k(2 ≤ k ≤ 4)장을 선택하고, 가로로 나란히 정수를 만들기로 했다. 상근이가 만들 수 있는 정수는 모두 몇 가지일까?

예를 들어, 카드가 5장 있고, 카드에 쓰여 있는 수가 1, 2, 3, 13, 21라고 하자. 여기서 3장을 선택해서 정수를 만들려고 한다. 2, 1, 13을 순서대로 나열하면 정수 2113을 만들 수 있다. 또, 21, 1, 3을 순서대로 나열하면 2113을 만들 수 있다. 이렇게 한 정수를 만드는 조합이 여러 가지 일 수 있다.

n장의 카드에 적힌 숫자가 주어졌을 때, 그 중에서 k개를 선택해서 만들 수 있는 정수의 개수를 구하는 프로그램을 작성하시오.

입력

첫째 줄에 n이, 둘째 줄에 k가 주어진다. 셋째 줄부터 n개 줄에는 카드에 적혀있는 수가 주어진다.

출력

첫째 줄에 상근이가 만들 수 있는 정수의 개수를 출력한다.

문제 풀이

4
2
1
2
12
1
답 : 7

예시로 12, 112, 11, 21, 212, 121, 122가 될 수 있다.
순열과 조합, n과 m 문제를 풀 때와 비슷하게 풀면 될 것 같다는 생각이 들었다.

4개 중 2개를 뽑을 때, 인덱스로 예를 들면 (0, 2) 과 (2, 0)을 모두 고려해야한다.
(0, 2) => 112
(2, 0) => 121
이렇게 조합했을 때 다른 숫자가 만들어지기 때문이다.

즉, 숫자는 같아도 순서가 다르면 다른 경우로 고려하기 때문에 순열로 풀어야 한다.

이런 식으로 재귀함수로 구현하고, depth(num)이 k가 되었을 때에 모아둔 숫자를 join으로 합친 후 결과에 저장한다.

결과 변수는 중복을 제거하기 위해서 set 타입으로 지정해주었다.

// 백준 5568번 카드 놓기

const fs = require("fs");
const input = fs.readFileSync("input.txt").toString().trim().split("\n").map(Number);
const n = input.shift();
const k = input.shift();

let numbers = new Set();
let visited = Array(n).fill(false);

let temp = [];

const makeNumber = (num) => {
  if (num === k) {
    numbers.add(temp.join(""));
    return;
  }
  for (let i = 0; i < n; i++) {
    if (!visited[i]) {
      visited[i] = true;
      temp.push(input[i]);
      makeNumber(num + 1);

      visited[i] = false;
      temp.pop();
    }
  }
};

makeNumber(0);
console.log(numbers.size);