[JavaScript] 백준 골드 5 : 1174 - 줄어드는 수

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

1174번: 줄어드는 수

---

📌 작성한 코드 

// 1174
const fs = require("fs");
const filePath = process.platform === "linux" ? "/dev/stdin" : "Beakjoon/Gold/test.txt";
let input = fs.readFileSync(filePath).toString().trim();

const N = Number(input);

let list = new Set([]);

const backTracking = (num, count) => {
    if (count === 10) {
        if (!list.has(num)) list.add(num);
        return;
    }

    backTracking(num, count + 1);
    backTracking(num * 10 + 9 - count, count + 1);
};

backTracking(0, 0);

const sorted = [...list].sort((a, b) => a - b);

if (N <= list.size) {
    console.log(sorted[N - 1]);
} else {
    console.log(-1);
}

 

📌 설명 

줄어드는 수 중 가장 큰 수는 9876543210 -> 10자리의 숫자이다.

그러므로 숫자의 길이가 10 초과인 수가 나올 수 없으니 길이가 10 이하인 숫자만 구하면 답을 구할 수 있다.

 

백트래킹으로 줄어드는 수 선택하기

- 수를 선택할 때 두가지 갈림길이 존재한다. 현재 숫자를 선택하지 않는 것과, 현재 숫자를 선택해서 숫자의 뒤의 추가하는 것.

(1) 현재 숫자를 선택하지 않기 : count를 증가시켜 숫자의 길이만 증가시키고, 숫자는 그대로 둔다 

- ex) 현재 숫자가 43이고 count가 8이라면 432 이렇게 추가하는 것이 아니라 43을 그대로 두고 count만 9로 증가시킨다. 

(2) 현재 숫자 선택하기 : 숫자에 10을 곱해서 자리수를 증가시키고, 맨 마지막에 현재 숫자를 더해서 새로운 줄어드는 수를 구한다. 

const backTracking = (num, count) => {
    if (count === 10) {
        if (!list.has(num)) list.add(num); // 자리수가 10이 되면 숫자 있는지 확인하고 추가 
        return;
    }

    backTracking(num, count + 1); // 새로운 숫자 선택 안하기 
    backTracking(num * 10 + 9 - count, count + 1); // 새로운 숫자 선택하기 
};

이렇게 모든 줄어드는 수를 구한 뒤에 숫자를 정렬해서, N번째에 해당하는 줄어드는 수를 출력한다. 

const sorted = [...list].sort((a, b) => a - b);

if (N <= list.size) {
    console.log(sorted[N - 1]);
} else {
    console.log(-1);
}

 

✅ 성공