백준_카드 놓기_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

예제 입력 2

6
3
72
2
12
7
2
1

예제 출력 2

68

Code(순열 이용한 풀이)

const fs = require('fs');
const input = fs.readFileSync('/dev/stdin').toString().trim().split('\n');

const n = +input[0]; // 카드 n장
const k = +input[1]; // 뽑을 카드 수
const cards = [];
for (let i = 2; i < 2 + n; i += 1) cards.push(input[i]);

// 순열
const permutationFunc = (arr, selectedNum) => {
  if (selectedNum === 1) return arr.map((a) => [a]);
  const result = [];
  arr.map((fixed, index, origin) => {
    const rest = [...origin.slice(0, index), ...origin.slice(index + 1)];
    const permutation = permutationFunc(rest, selectedNum - 1);
    const attached = permutation.map((item) => [fixed, ...item]);
    result.push(...attached);
  });
  return result;
};

const permutationResult = permutationFunc(cards, k);
const set = new Set();
permutationResult.forEach((permu) => set.add(+permu.join('')));
console.log(set.size);

풀이 및 해설

• 순열과 집합(Set) 이용
  1. n개의 리스트 중 k개 선택하는 총 순열 배열 구하기
  2. 순열 배열 순회하면서 집합 set에 연결시킨 숫자 집어넣기
  3. 집합 set의 총 길이 리턴

Code(백트래킹)

const fs = require('fs');
const input = fs.readFileSync('/dev/stdin').toString().trim().split('\n');

const n = +input[0]; // 카드 n장
const k = +input[1]; // 뽑을 카드 수
const cards = [];
for (let i = 2; i < 2 + n; i += 1) cards.push(input[i]);

// 백트래킹
const backtrackingSet = new Set();
const visited = Array.from({ length: 11 }, () => false);
const backtracking = (depth, selected) => {
  if (depth === k) {
    backtrackingSet.add(selected.join(''));
    return;
  }
  for (let i = 0; i < n; i += 1) {
    if (!visited[i]) {
      visited[i] = true;
      selected.push(cards[i]);
      backtracking(depth + 1, selected);
      selected.pop();
      visited[i] = false;
    }
  }
};

backtracking(0, []);
console.log(backtrackingSet.size);

풀이 및 해설

• 백트래킹과 집합(Set) 이용
  1. depth가 k가 될때까지 방문하지 않은 숫자 넣으며 백트래킹 이용
  2. depth가 k가 되면 selected안에 들어있는 문자 결합하여 집합 set에 넣기
  3. 집합 set의 총 길이 리턴

---

처음에 순열로 이용해서 풀었는데 백트래킹 이용해서 푸는 방법을 보고 다시 풀어보았다.
순열보다 백트래킹으로 푸는 것이 메모리와 시간 효율 측면에서 훨씬 더 좋다!