백준/ Silver 5 문제 , 백준 Node.js 자바스크립트 18511, 큰 수 구성하기 [완전탐색]

백준/ Silver 5 문제 , 백준 Node.js 자바스크립트 18511, 큰 수 구성하기 [DFS]

 

 

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

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

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

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

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

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

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

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


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

 

 

 

문제 출처 🏠

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

18511번: 큰 수 구성하기

 

 

문제풀이 소감 🧑‍💻

dfs 로 모든 경우의 수를 조합해서 찾았는데, 자릿수 범위가 처음에 헷갈렸다.

실버 5 치고는 구현이 좀 필요한편.

 

 

요구사항 📋

 

N보다 작은 K의 원소로만 이루어진 모든 숫자들중에서 가장 큰 값을 찾아라

 

 

주의 ❗

자릿수 주의!!

 

자릿수가 따로 명시되어있지 않아서 K개의 자릿수를 유지했는데, 그게 아니고 K개의 자릿수 이하도 모두 포함이다.

 

예를 들어 K가 3이라고 3자릿수 숫자만 확인하는 것이 아닌 한자리 두자리 숫자도 모두 확인해야한다.

 

K의 원소로만 구성만 되어있으면 된다.

 

 

 

해결 전략 📝

dfs 로 N의 길이 이내의 자릿수들을 모두 찾아내어 정렬한 뒤 그중 N보다 작으면서 가장 큰값을 찾자.

 

 

 

 

정답 💯

 

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

const [input_N, input_K] = input[0].split(" ").map(Number);
const [...input_nums] = input[1].split(" ").map(Number);

function solution(N, K, nums) {
  const dfs = (makeNum, idx) => {
    if (idx === String(N).length) {
      return;
    }

    for (let i = 0; i < K; i++) {
      makeNum.push(nums[i]);
      numStore.push(Number(makeNum.join("")));
      dfs(makeNum, idx + 1);
      makeNum.pop();
    }
  };

  let numStore = [];
  dfs([], 0);
  numStore = numStore.sort((a, b) => a - b);

  for (let i = 0; i < numStore.length; i++) {
    if (numStore[i] > N) {
      return numStore[i - 1];
    }
  }

  return numStore[numStore.length - 1];
}

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