[JavaScript/백트래킹] 백준 실버 2 : 6603 - 로또

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

6603번: 로또

---

📌 작성한 코드 

// 6603
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 LOTTO_COUNT = 6;

while (true) {
    const temp = input.shift();
    if (temp === "0") break;
    const [k, ...list] = temp.split(" ").map(Number);

    let arr = new Array(6).fill(0);
    let visited = new Array(list.length).fill(false);
    let answer = "";

    const backTraking = (at, count) => {
        if (count === LOTTO_COUNT) {
            answer += `${arr.join(" ")}\n`;
            return;
        }

        for (let i = at; i < k; i++) {
            if (!visited[i]) {
                arr[count] = list[i];
                visited[i] = true;
                backTraking(i + 1, count + 1);
                visited[i] = false;
            }
        }
    };

    backTraking(0, 0);
    console.log(answer);
}

📌 설명 

숫자를 선택해서 수열을 만드는 경우에는 백트래킹을 이용하면 간단하게 해결할 수 있다. 

N과 M 문제 시리즈를 풀어보았다면 간단하게 문제를 해결할 수 있을 것이다.

 

(1) 제약 조건 확인하기 

해당 백트래킹을 할 때 신경 써야 하는 부분은

- 같은 수를 여러번 선택할 수 없다. (로또 번호니까 당연하다)

- 사전순으로 출력해야 한다.(순서가 다른 수열을 생성할 필요가 없다. 사전순으로 정렬된 수열만 생성한다)

 

(2) 제약 조건 신경써서 코드 작성하기

const backTraking = (at, count) => {
        if (count === LOTTO_COUNT) {
            answer += `${arr.join(" ")}\n`;
            return;
        }

        for (let i = at; i < k; i++) { // 사전순으로 출력해야 하니까 더 큰 숫자만 선택해야함 -> at으로 관리
            if (!visited[i])  // 방문하지 않은 숫자라면 -> 중복을 방지하기 위하여
                arr[count] = list[i];
                visited[i] = true;
                backTraking(i + 1, count + 1); // 현재 보다 큰 숫자부터 접근하도록 i+1 
                visited[i] = false;
            }
        }
    };

 

✅ 성공