[Baekjoon]5568번 카드 놓기 - Javascript

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

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개 줄에는 카드에 적혀있는 수가 주어진다.

출력

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

예제 입력 1 복사

4
2
1
2
12
1

예제 출력 1 복사

7

 

문제풀이(1)

n개의 카드중에서 k개의 카드만 나열하여 만들 수 있는 중복이 제거된 정수들의 수를 구하는 순열, 조합 문제이다.
중복을 제거하기 위해 set을 사용한다.
dfs로 탐색한다.

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

const combinations = new Set();
const selectedCards = [];
const visitedCards = new Array(n).fill(false);

findDistinctCombinations(selectedCards, visitedCards);

console.log(combinations.size);

function findDistinctCombinations(selected, visited) {
  // 선택된 카드의 개수가 k랑 같을 경우 조합에 추가
  if (selected.length === k) {
    combinations.add(selected.join(""));
    return;
  }

  for (let i = 0; i < cards.length; i++) {
    // 선택되지 않은 카드들의 조합을 찾기위함
    if (!visited[i]) {
      visited[i] = true;
      selected.push(cards[i]); // 선택된 카드에 추가
      findDistinctCombinations(selected, visited); // 재귀
      visited[i] = false;
      selected.pop();
    }
  }
}