[JS][TIL] DFS를 이용한 순열구하기 : 프로그래머스 피로도, 소수 찾기

순열이란?

서로 다른 n개의 원소에서 r개를 중복없이 순서를 고려하여 선택하거나 나열하는 것.

[1, 2, 3]에서 2개를 중복없이 순서를 고려하여 선택 및 나열한다면 [1, 2], [1, 3], [2, 1], [2, 3], [3, 1], [3, 2] 이다.

(조합은 순서를 고려하지 않고 선택 및 나열하는 것. 위와 같은 예시에서 조합을 구한다면 [1, 2], [1, 3], [2, 3])

JavaScript로 순열 구현하기

1. 선택할 원소 개수 r이 정해져 있을 때

ref: https://www.youtube.com/watch?v=0tcgYHU8IIs

function permutate(arr) {
    const results = [];
    
    // DFS
    const dfs = (i, arr) => {
        // base condition
        if (i === arr.length) {
            return results.push([...arr]);
        }
        
        for (let j = i; j < arr.length; j++) {
            // swap
            [arr[i], arr[j]] = [arr[j], arr[i]];
            
            // dfs
            dfs(i + 1, arr);
            
            // swap back (백트랙킹)
            [arr[i], arr[j]] = [arr[j], arr[i]];
        }
    }
    dfs(0, arr);
    return results;
}

2. 선택할 원소 개수 r이 정해져 있지 않을 때

const getPermutations= function (arr, selectNumber) {
    const results = [];
    
    if (selectNumber === 1) return arr.map((value) => [value]); // 1개씩 택한다면 모든 배열의 원소 return

    arr.forEach((fixed, idx, origin) => {
        const rest = [...origin.slice(0, idx), ...origin.slice(idx + 1)] // fixed 제외한 나머지
        const permutations = getPermutations(rest, selectNumber - 1); // 나머지에 대한 순열
        const attached = permutations.map((permutation) => [fixed, ...permutation]); // fixed 붙이기
        results.push(...attached);
    });

    return results;
};

---

[프로그래머스 level 2] 소수 찾기

접근방식

1. 문자열 numbers를 한 글자씩 split해 종이 조각(한자리 숫자)들을 구한다. (배열 number에 저장)
2. 종이 조각으로 만들 수 있는 모든 수를 구한다. (빈 배열 answer에 저장)
3. answer에 저장된 수 중 소수를 찾는다.

순열을 활용해 2단계에서 number의 요소들을 조합해 만들 수 있는 모든 수를 구해야겠다고 생각했다.

입출력 예 1의 경우 1단계를 거친 후 number = ["1","7"] 가 된다. 이를 조합해 1, 7, 17, 71을 만들기 위해서는

 

1. number에서 1개의 원소를 순서 고려 & 중복 없이 조합하는 경우와
2. number에서 2개의 원소를 순서 고려 & 중복 없이 조합하는 경우를 고려해야 한다.

따라서 for문을 통해 순열의 r이 1부터 number.length인 순열을 모두 구해 배열 answer에 넣어준다. ➡️ 위에 작성한 순열 구현 방식 2 사용

 

소수는 에라토스테네스의 체를 이용해 찾았다.

2023.10.15 - [Algorithm & Data structure/알고리즘 문제 풀이] - [Python][백준 BOJ Silver Ⅱ] 9020. 골드바흐의 추측 : 에라토스테네스의 체, 범위 내에 존재하는 모든 소수

✅ Solution

const getPermutations= function (arr, selectNumber) {
    const results = [];
    
    if (selectNumber === 1) return arr.map((value) => [value]); // 1개씩 택한다면 모든 배열의 원소 return

    arr.forEach((fixed, idx, origin) => {
        const rest = [...origin.slice(0, idx), ...origin.slice(idx + 1)] // fixed 제외한 나머지
        const permutations = getPermutations(rest, selectNumber - 1); // 나머지에 대한 순열
        const attached = permutations.map((permutation) => [fixed, ...permutation]); // fixed 붙이기
        results.push(...attached);
    });

    return results;
};

function solution(numbers) {
    const number = numbers.split('');
    const answer = [];
    
    for (let r = 1; r <= number.length; r++) {
        let permutations = getPermutations(number, r);
        answer.push(...permutations.map(p => p.join('')));
    }
    
    const uniqueAnswer = [...new Set(answer.map(n => Number(n)))]
    let primeCnt = 0;
    uniqueAnswer.forEach(n => {
        if (n < 2) return false;
        
        for (let i = 2; i <= Math.sqrt(n); i++) {
            if(n % i === 0) return false;
        }
        
        primeCnt++;
    })
    
    return primeCnt;
}

순열을 구하는 for문에서 answer.push(permutations); 와 같이 작성하면 answer = [[["1"],["7"]],[["1","7"],["7","1"]]] 이다.

join을 통해 answer = ["1", "7", "17", "71"]; 형태로 만들어준 후 숫자형변환을 해주었다. 

 

입출력 예 2의 numbers는 011이다. 이 경우 answer에 중복되는 값이 있으므로 (Number로 형변환해서 11이 두개 생김("011", "11")) 세트로 형변환하고, 다시 배열로 만들어 중복되는 값을 없앴다.

 

---

[프로그래머스 level 2] 피로도

접근방식

1. 던전 탐험 순서의 모든 경우의 수를 구한다. (배열 casePath에 저장)
2. casePath를 순회하며 탐험할 수 있는 던전 개수를 구한다. (+ 최댓값 기록)
3. 만약 던전 개수(dungeons.length)와 탐험 가능한 던전 개수가 같다면 더이상 순회하지 않고 바로 최댓값 반환!

던전 탐험 순서의 모든 경우의 수를 구하기 위해 순열을 이용했다. ➡️ 위에 작성한 순열 구현 방식 1 사용

✅ Solution 1 - 탐험 순서 순열 구하기

function permutate(arr) {
    const cases = [];   // 탐험 순서 경우의 수
    
    // DFS
    const dfs = (i, arr) => {
        // base condition
        if (i === arr.length) {
            return cases.push([...arr]);
        }
        
        for (let j = i; j < arr.length; j++) {
            [arr[i], arr[j]] = [arr[j], arr[i]];	// swap
            
            dfs(i + 1, arr);	// dfs
            
            [arr[i], arr[j]] = [arr[j], arr[i]];	// swap back (백트랙킹)
        }
    }
    dfs(0, arr);
    return cases;
}

function solution(k, dungeons) {
    const casePath = permutate(dungeons.map((dungeon, idx) => idx));
    let ans = 0;
    
    casePath.forEach(path => {
        let piro = k;
        let cnt = 0;
        
        path.forEach(i => {
            if (piro >= dungeons[i][0]) {
                piro -= dungeons[i][1];
                cnt ++;
            } else return false;
        })
        
        ans = Math.max(ans, cnt)
        if (ans === dungeons.length) return false;
    })
    
    return ans;
}

✅ Solution 2 - 정석 dfs 풀이

solution1으로 문제를 맞춘 후 다른 사람들의 풀이를 보았다.

정석적인 dfs 방식을 사용하는걸 보고 위처럼 풀 필요가 없었다는 것을 느끼며 다시 풀어보았다 ....^^...

function solution(k, dungeons) {
    let ans = 0;
    const visited = new Array(dungeons.length).fill(0);
    
    function dfs(k, cnt) {
        ans = Math.max(ans, cnt)
        if (ans === dungeons.length) return;
        
        for (let i = 0; i < dungeons.length; i++){
            if (k >= dungeons[i][0] && !visited[i]) {
                visited[i] = 1;
                dfs(k - dungeons[i][1], cnt + 1);
                visited[i] = 0;
            }
        }
    }
    
    dfs(k, 0);
    return ans;
}

 

순열은 꼬옥 필요할 때만 구현하는 걸로 ^^ㅎ

Solution 1로 푼 결과 0.87ms가 걸렸고, Solution 2로 다시 풀어보니 0.18ms가 걸렸다.

---

https://school.programmers.co.kr/learn/courses/30/lessons/42839

프로그래머스

https://school.programmers.co.kr/learn/courses/30/lessons/87946

프로그래머스