[JavaScript/백트래킹] 백준 실버 2 : 15663 - N과 M (9)

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

15663번: N과 M (9)

---

📌 작성한 코드 

// 15663
const fs = require("fs");
const filePath = process.platform === "linux" ? "/dev/stdin" : "Beakjoon/Silver/test.txt";
const input = fs.readFileSync(filePath).toString().trim().split("\n");

const [N, M] = input[0].split(" ").map(Number);
const numbers = input[1]
    .split(" ")
    .map(Number)
    .sort((a, b) => a - b);

let arr = new Array(M).fill(0);
let isUsed = new Array(N).fill(false);
let answer = "";

const tracking = (count) => {
    if (count === M) {
        answer += `${arr.join(" ")}\n`;
        return;
    }

    let prev = 0;
    for (let i = 0; i < N; i++) {
        if (!isUsed[i] && numbers[i] !== prev) {
            arr[count] = numbers[i];
            prev = numbers[i];

            isUsed[i] = true;
            tracking(count + 1);
            isUsed[i] = false;
        }
    }
};

tracking(0);
console.log(answer);

📌 풀이 

백트래킹을 이용하여 N개의 숫자들을 조합하여 M의 길이로 이루어진 수열을 구하는 문제이다.

 

다른 N과 M 문제와 다르게 특별하게 있는 조건은 이것이다. 

(1) 주어지는 N개의 숫자들 중 중복된 숫자가 있을 수 있다는 점

(2) N=[1,9,9]일 때, [1,1] 이렇게 중복된 수열은 출력하면 안되지만 [9,9]같이 숫자가 2개 있어서 만들 수 있는 수열은 출력해야 한다.

 

해당 문제에서 중복된 숫자만 해당 횟수만큼 사용하고, 다른 숫자를 여러번 사용하지 않기 위해서 이전 항의 숫자와 겹치는지를 확인할 것이다.

 

왜 숫자 전부를 확인하지 않고 마지막 숫자만 확인해도 중복을 확인할 수 있을까?

(1) 정렬된 숫자들을 사용하고 있기 때문에

-> 수열을 사전순으로 출력하기 위해서 문제를 풀 때 N을 정렬해서 사용하고 있다.

-> 정렬되어 있고, 순차적으로 접근하고 있어서 9와 같이 중복된 수가 있을 때는 N 배열안에 둘이 나란히 들어가 있다.

-> [9,1,9] 이런식이라면 직전 숫자를 확인한다고 해도 중복되는 수열이 존재하는지 확인 할 수 없다.

-> [1,9,9] 이렇게 정렬되어 있으면 바로 앞 숫자만 확인해서 중복되는지 확인하면 된다. 

 

(2) 이미 수열에 들어간 숫자는 중복이 걸러진 수열이기 때문에

-> [1,7][1,9][1,9]가 나온 상태에서 이전 수열의 마지막 숫자인 9가 중복되는 것을 확인하고 마지막 수열은 버린다.

-> 그 다음 숫자를 고를 때 [1,7], [1,9] 수열 다음에 올 숫자를 고를 차례인데, 이렇게 앞에 저장된 수열들은 이미 중복이 걸러졌다.

-> 이제 중복이 나올 수 있는 방법은 마지막 숫자가 같은것이 나오는 것뿐이다. 

 

-> 이전 수만 확인해도 중복되는지 확인할 수 있다!

 

그래서 이전 수열의 마지막 수와 동일한지 체크하는 로직을 추가해주면 된다. 

let prev = 0; // 이전 수열의 마지막 수 저장할 변수
for (let i = 0; i < N; i++) {
    if (!isUsed[i] && numbers[i] !== prev) { // 같은지 확인
        arr[count] = numbers[i];
        prev = numbers[i]; // 마지막 수 업데이트

        isUsed[i] = true;
        tracking(count + 1);
        isUsed[i] = false;
    }
}

 

📌 참고

왜 이전 항의 숫자와 비교해야 하는지 더 잘 알려주는 블로그이다. 나보다 더 잘 설명하고 있으니 읽어보는 것을 추천한다.

https://blog.naver.com/js568/221857286945

[백준] 15663번 : N과 M (9) c++

 

✅ 성공