[백준] 18511 큰 수 구성하기 JavaScript

혅·2024년 7월 4일

JavaScript

백준, 프로그래머스 -JavaScript-

목록 보기

112/215

문제

N보다 작거나 같은 자연수 중에서, 집합 K의 원소로만 구성된 가장 큰 수를 출력하는 프로그램을 작성하시오. K의 모든 원소는 1부터 9까지의 자연수로만 구성된다.

예를 들어 N=657이고, K={1, 5, 7}일 때 답은 577이다.

입력

첫째 줄에 N, K의 원소의 개수가 공백을 기준으로 구분되어 자연수로 주어진다. (10 ≤ N ≤ 100,000,000, 1 ≤ K의 원소의 개수 ≤ 3) 둘째 줄에 K의 원소들이 공백을 기준으로 구분되어 주어진다. 각 원소는 1부터 9까지의 자연수다.

단, 항상 K의 원소로만 구성된 N보다 작거나 같은 자연수를 만들 수 있는 경우만 입력으로 주어진다.

출력

첫째 줄에 N보다 작거나 같은 자연수 중에서, K의 원소로만 구성된 가장 큰 수를 출력한다.

예제 입력

657 3
1 5 7

예제 출력

577

내가 했던 풀이 방법

max를 0으로 초기화해준다.
DFS는 number를 파라미터로 받는다. 이때 number는 배열 형태로 join을 이용해 문자열로 변환한 뒤, Number형으로 변환해주어야 한다. Number형으로 변환된 값을 num에 저장해준다.
num이 N보다 클 경우, 의미없는 연산이 되므로 return 해준다.
max값보다 현재 num이 클 경우, max를 num으로 바꿔준다.
number의 길이 즉, 현재까지의 number의 자릿수가 N의 자릿수와 같아질 경우 return 해준다. (4번에서 max값 저장해주는 과정을 진행해주었기 때문에 return만 해주면 된다. max는 5번 조건 외에도 필요한 과정이므로, 재귀를 할 때마다 유효한 재귀일 경우 max 값이 계속 변하게 된다.)
K의 원소를 현재 number의 마지막 요소로 추가해 DFS를 재호출해준다.
DFS가 모두 끝난 후, max 값을 출력한다.

코드

const fs = require('fs');
let [n, element] = fs.readFileSync(0, 'utf-8').toString().trim().split('\n');

let [N, K] = n.trim().split(' ').map(Number);
element = element.trim().split(' ').map(Number);
let max = 0;

function DFS(number) {
  let num = Number(number.join(''));
  if (number.length > 0 && num > N) return;
  if (max < num) max = num;

  if (number.length === N.length) return;

  for (let i = 0; i < K; i++) {
    DFS([...number, element[i]]);
  }
}

DFS([]);
console.log(max);

회고

보통 DFS를 풀이할 때 끝나는 조건이 있고, 끝나는 조건과 함께 현재까지의 결과를 저장하는 과정을 추가하는 과정으로 진행되었는데, 이 코드에서는 다소 달랐다. (물론 그렇게해서 구할 수...있을지도 모르지만) 이 문제에서 가장 힘들었던 부분은 꼭 둘의 자릿수가 동일하지 않다는 것이다. 애를 먹었던 입력 예시가 있는데 아래와 같다.