[프로그래머스] 후보키

📙 1. 문제

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

문제 설명

 

풀이 1 : DFS 깊이 우선 탐색

풀이 과정

1. 문제를 읽어보면 다른 꼼수 없이 모든 경우의 수를 탐색해야 함을 직감할 수 있다. 그래서 나는 DFS와 BFS 중에 고민했다.

2. 그렇다면 왜 BFS가 아니라 DFS인가? 문제에서 후보 키는 1. 유일성 2. 최소성을 만족시켜야 한다고 했다. 그래서 중간에 두 조건 중 하나라도 만족하지 않으면 stop 하는 알고리즘을 짜기 위해 DFS로 구현하였다. 그러나, 결국 모든 조합을 완성하고, 위 두 조건을 체크하기에 DFS와 BFS는 시간 복잡도가 동일할 것이다. BFS로 구현해도 괜찮으니, DFS와 BFS 중 편한 알고리즘으로 구현하면 될 것이다.

3. rowCount, columnCount는 각각 열의 크기, 행의 크기이다. 실수를 줄이기 위해 미리 변수화하였다.

4. 후보 키의 두 조건 1. 유일성 2. 최소성을 각각 함수 isOnly, isLeast로 함수화 하였다. 함수 내에서는 각각 for가 아닌 forEach를 사용함으로써 함수형 프로그래밍의 선언형 프로그래밍('무엇'을 할 것인지를 설명하는 방식)을 유지하였다.

 

 

function solution(relation) {
    var answer = 0;
    const rowCount = relation[0].length
    const columnCount = relation.length
    const isOnly = (arr) =>{
        const tempArr = [];
        let isOnly = true;
        relation.forEach(item=>{
            const str = arr.map(index=>item[index]).join('')
            if(tempArr.includes(str)) isOnly=false;
            else tempArr.push(str)
        })
        return isOnly;
    }
    const accArr = [];
    const isLeast = (arr) =>{
        let isLeast = true;
        accArr.forEach(item=>{
            if(item.every(it=>arr.includes(it))) isLeast=false;
        })
        return isLeast
    }
    const stack = [];
    const dfs = (maxCount,stack,now) => {
        if(stack.length===maxCount){
//             1. 유일성
            if(!isOnly(stack)) return;
//             2. 최소성
            if(!isLeast(stack)) return;
            accArr.push(stack)
            return;
        }
        for(let i=now;i<rowCount;i++){
            dfs(maxCount,[...stack,i],i+1)
        }
    }
    for(let i=1;i<=rowCount;i++){
        dfs(i,[],0)    
    }
    return accArr.length;
}

---

🤔 2. 느낀 점

코드 작성 능력이 향상되었다는 것을 느꼈다. 최대한 사이드 이펙트가 없는 함수를 만들기 위해 DFS에서 사용하는 maxCount, stack, now를 매개변수로 전달했다. 함수화하고 순수 함수를 만들었더니, 실수가 줄어들고 코드의 유지보수성이 향상되었다는 것을 명확하게 알 수 있었다. 코드가 전보다 더욱 깔끔해지고 구조가 더욱 명확해졌다. 이를 계기로 JavaScript의 함수형 프로그래밍 원칙을 준수하고, 클린 코드 작성 및 우수한 문제 해결 전략을 계속 배워나갈 것이다.

이번 문제 해결에서 배열을 결합하여 문자열로 변환하고 이를 배열에 추가하는 방법은 이전에 다루었던 문제에서 배운 것이다. 문제를 해결하면서 느낀 것은, 경험을 쌓는 것이 매우 중요하다는 점이다. 만약 이런 문제 해결 방법을 이전에 배우지 않았다면, 이런 방식으로 문제를 해결할 수 있었을지 의문이다. 아마도 생각 자체를 못하거나, 생각은 했지만 중간에 막혀서 포기했을 것이다. 앞으로 다양한 문제를 계속해서 풀어보면서 경험을 쌓아나가야겠다.