[프로그래머스] 후보키(LV.2) by javascript - 2019 KAKAO BLIND RECRUITMENT

원래 알고리즘 문제풀이 관련하여 게시글을 작성할 생각은 없었는데, 그래도 블로그의 개인적인 이유가 나의 성장과정을 보고 싶기 때문이니 이것도 정리하면 좋겠다 싶었다.

 

후보키 문제를 기준으로 지금까지 해결한 문제와 앞으로 해결할 문제들의 일부분을 계속해서 올릴 생각이다.

---

▷ 문제 : 2019 KAKAO BLIND RECRUITMENT - 후보키 LV.2

코딩테스트 연습 - 후보키

 

▷ 해결 날짜 : 2022.03.09

▷ 소요 시간 : 2시간

▷ 풀이 과정 :

역시 카카오 문제다 보니 지문부터가 심상치 않다.

데이터베이스에 관련된 후보키의 개수를 추출하는 문제인데, 핵심은 최소성과 유일성을 체크하는 과정이다.

몇십 분 동안 지문을 읽고 어떻게 풀어나가야 할지 고민하던 중 결국, 모든 경우의 수를 조합해  유일성과 최소성을 체크해주면 되겠구나 싶었다.

 

이제 방향을 잡았으니 구현을 해야하는데, 여기서 또 이중 배열이 걸린다 조합을 어떻게 구하지...? 라는 의문과 함께 여기서도 시간이 걸렸다.

배열 값들의 조합을 구할려고 하니 막막했는데, 배열은 배열 그냥 인덱스 조합을 구하는 것으로 방향을 잡으니 손쉽게 풀렸다.

 

다음 구현 코드를 보면 알겠지만 우선 조합 알고리즘을 통해 모든 후보키의 경우의 수를 구하고 거기서 유일성과 최소성을 순서대로 구해주었다.

 

▷ 구현

function solution(relation) {
    let idxArr = Array.from(Array(relation[0].length), (v, i) => i);
    let combinations = [];
    for(let i = 0 ; i < idxArr.length ; i++){
        combinations.push(...getCombination(idxArr, i + 1));
    }

    combinations = checkUniqueness(relation, combinations);
    combinations = checkMinimality(combinations);

    return combinations.length;
}

const checkUniqueness = (arr, comb) => {
    const results = [];
    comb.forEach((v1, i1) => {
        let set = new Set();
        arr.forEach((v2, i2) => {
            set.add(v1.map(e => v2[e]).join(','));
        });

        if(set.size == arr.length) results.push(v1);
    });

    return results;
}

const checkMinimality = (comb) => {
    const results = [];

    while(comb.length){
        results.push(comb[0]);
        comb = comb.reduce((a, c) => {
            let check = comb[0].every(e => c.includes(e));
            if(!check) a.push(c);
            return a;
        },[]);

    }

    return results;
}

const getCombination = (arr, num) => {
    const results = [];
    if(num === 1) return arr.map(v => [v]);

    arr.forEach((fixed, index, origin) => {
        const rest = origin.slice(index + 1);
        const combinations = getCombination(rest, num - 1);
        const attached = combinations.map(v => [fixed, ...v]);
        results.push(...attached);
    });

    return results;
}

 

▷ 복기 : 

역시 너무 어렵다...

구현하는 시간보다 해결 방향을 잡는데 오랜 시간이 걸려버렸다.

구현에서는 조합 알고리즘 자체는 쉽게 구현하였는데 최소성을 구하는 단계에서 자꾸 틀리는 경우가 생겨 헤맸다.

좀 더 코드를 단순화 시킬 수 있지 않을까? 라는 생각이 들기는 하지만 성능을 더 당길 수는 있을지 의문이다.

 

2단계 문제가 이정도면 도대체 3~5단계는 뭘까...