백준/ Silver 4 문제 , 백준 Node.js 자바스크립트 5568 카드 놓기 [완전탐색]

백준/ Silver 4 문제 , 백준 Node.js 자바스크립트 5568 카드 놓기 [완전탐색]

 

 

✔️Check Point !   ( 해당사항 ✓체크 )

1. 막힘 없이 수월하게 풀린 문제인가?

2. 1시간이내로 풀렸던 문제인가?

3. 1시간 이상 or 며칠을 두고 풀어봤더니 풀린 문제인가?

4. 시간을 써도 도무지 풀 수 없는 문제인가?

5. 솔루션을 찾아봤는가?

-------------------------------------------------------------------------------------------

난이도 체감 🧑‍💻
1. 최상
2. 상
3. 중
4. 하


이해도 🙆‍♂️
1. 완벽히 이해
2. 다소 헷갈리는 부분들이 있음
3. 이해 못함

 

 

 

문제 출처 🏠

 

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

5568번: 카드 놓기

 

 

문제풀이 소감 🧑‍💻

백트래킹으로 풀 수 있는 문제이다. N과 M 문제 시리즈를 풀어봤다면 손쉽게 풀 수 있을거에요

 

 

요구사항 📋

N개의 숫자들 중 K개만 뽑아서 만들 수 있는 모든 숫자들의 갯수를 구하여라.

 

 

주의 ❗

중복은 카운트 안한다.

 

 

 

해결 전략 📝

백트래킹으로 모든 경우의 수들을 탐색하는데 중복된 숫자는 카운트 하지 않기 위해 dict에 나왔던 숫자들을 모두 저장해가면서 dict 에 담겨있다면 cnt 해주지 않는 방식으로 cnt 해준다.

또한, 한 번 사용한 숫자는 또 사용할 수 없기 때문에 visited 로 방문 체크를 해준다.

 

 

정답 💯

 

 

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

const [input_N, input_K, ...input_nums] = input.map(Number);

function solution(N, K, nums) {
  const dfs = (idx) => {
    if (idx === K) {
      if (!dict[makeStr.join("")]) {
        cnt += 1;
        dict[makeStr.join("")] = true;
      }
      return;
    }

    for (let i = 0; i < N; i++) {
      if (!visited[i]) {
        makeStr.push(nums[i]);
        visited[i] = true;
        dfs(idx + 1);
        visited[i] = false;
        makeStr.pop();
      }
    }
  };

  const dict = {};
  let visited = Array.from({ length: N }).fill(false);
  let makeStr = [];
  let cnt = 0;
  dfs(0);

  return cnt;
}

console.log(solution(input_N, input_K, input_nums));