카드 놓기

카드 놓기

문제 설명

상근이는 카드 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개를 선택해서 만들 수 있는 정수의 개수를 구하는 프로그램을 작성하시오.

예제 입력

4
2
1
2
12
1

예제 출력

7

---

문제 풀이

const fs = require("fs");
const path = require("path");
const input = fs
  .readFileSync(
    process.platform === "linux"
      ? "dev/stdin"
      : path.join(__dirname, "input.txt")
  )
  .toString()
  .trim()
  .split("\n");

const solution = (input) => {
  let idx = 0;
  const arr = [];
  const N = Number(input[idx++]);
  const K = Number(input[idx++]);
  for (let i = 0; i < N; i++) {
    arr.push(Number(input[idx++]));
  }

  const set = new Set();
  const visited = Array.from({ length: N }, () => false);

  const dfs = (depth, num) => {
    if (depth === K) {
      set.add(Number(num));
      return;
    }
    for (let i = 0; i < N; i++) {
      if (visited[i] === false) {
        visited[i] = true;
        dfs(depth + 1, num.toString() + arr[i].toString());
        visited[i] = false;
      }
    }
  };
  dfs(0, "");
  console.log(set.size);
};
solution(input);

아이디어

1. 동일한 수 넣지 않도록 Set 생성
2. 재귀 함수를 돌려가면서 depth가 K 에 도달하면 set에 추가
3. 재귀 함수 매개변수를 문자열로 받아서 1 + 1 = 11 과 같이 하도록 함
4. 재귀 호출 끝나면 visited 배열 원복

후기

코테 대비 문제 6