[JS] 후보키 - every를 아시나요?

안녕하세요.

오늘 다뤄볼껀 2019 카카오 블라인드 채용 기출문제인 후보키입니다.

카카오 문제는 역시 장황하네요.

자 다들 잘 푸셨나요? 같이 한번 보죠

---

문제 요약

아래와 같은 학생들의 인적사항이 주어졌을 때, 후보 키의 최대 개수를 구하라.

유일성과 최소성을 만족하는 키를 모두 구하시오.

relation	result
[["100","ryan","music","2"],["200","apeach","math","2"],["300","tube","computer","3"],["400","con","computer","4"],["500","muzi","music","3"],["600","apeach","music","2"]]	2

 

접근방법

일단 입력이 2중 배열로 되어있네요. 사실 어떤 칼럼을 키로 정했다면 나머지 칼럼은 의미가 없어집니다.

적절하게 relation을 조작해야겠다는 생각이 듭니다.

처음에는 테이블을 pivot 해볼까? 하는 생각이 들었다가 키를 여러개로 설정할 수도 있기에 좋은 방법은 아니라는 생각이 들었습니다.

 

결론적으로는 모든 칼럼에 대해서 가능한 조합을 모두 구한 다음 순회하면서 후보키를 만족한다면 그 키를 포함하는 경우를 가지치기하는 식으로 가기로 했습니다.

조금 더 정리해보죠.

 

1. 칼럼의 위치를 index로 하여 가능한 모든 조합을 구한다. (ex. [[0], [1], [2], [0, 1]....])
2. 조합을 순회하면서 칼럼들을 합칩니다. (ex. [0, 1] => ["100ryan", "200apeach"....])
3. 합쳐진 배열이 중복된 값이 없다면 후보키입니다. 갯수를 하나 세어줍니다.
4. 그렇다면 나머지 조합에서 [0, 1]이 포함된 경우는 더 이상 연산할 필요가 없습니다. 최소성의 원리에 위반되니까요.

이렇게 하면 될 것 같네요.

적절하게 filter와 includes를 이용하던 과정에 every라는 함수를 발견해서 한 번 써봤습니다. 아래에서 소개드릴게요.

 

정답 코드

function combinations (arr, level) {
    if (level === 1) return arr.map(v => [v]);
    const result = [];
    arr.forEach((item, i, origin) => {
        const rest = origin.slice(i + 1);
        const combis = combinations(rest, level - 1);
        const combination = combis.map(v => [item, ...v]);
        result.push(...combination);
    });
    return result;
}

function solution(relation) {
    const cols = Array.from({length: relation[0].length}, (_, i) => i);
    let count = 0;
    let combiLevel = 1;
    const allcases = []; // 모든 col index 의 조합을 담습니다.
    
    while (combiLevel <= cols.length) {
        allcases.push(...combinations(cols, combiLevel++));
    }
    
    const skip = []; //순회하다가 후보키로 등록되었다면 넣어줍니다.
    let cursor = 0;
    while (cursor < allcases.length) {
        const col = allcases[cursor];
        if (skip.filter(item => item.every(v => col.includes(v))).length !== 0) {
            cursor++;
            continue;
        }
        const key = relation.flatMap((val) => col.map(item => val[item]).join(""));
        if ([...new Set(key)].length === relation.length) {
            skip.push(col);
            count++;
        }
        cursor++;
    }
    return count;
}

팁 1. every에 대해서

if (skip.filter(item => item.every(v => col.includes(v))).length !== 0) {
    cursor++;
    continue;
}

skip은 이전 분기에서 등록된 모든 후보키가 들어갑니다.

예시에서 [0]의 칼럼은 후보키입니다. skip에 들어가게 되겠네요.

최소성의 법칙에 의해 [0]이 포함된 [0, 1], [0, 2], [0, 1, 2] 와 같은 조합은 순회할 필요가 없습니다.

그렇기 때문에 skip의 배열의 모든 요소가 지금 현재 순회 대상 조합에 전부 존재하는가? 를 확인해줘야합니다.

이럴 때 정말 유용하게 쓸 수 있는게 이 every입니다.

 

number 배열안에 number가 있는지 확인을 위해서는 filter나 includes를 쓰면 되지만,
특정 배열안의 모든 요소가 다른 배열안에 있는지 확인을 위해서는 every를 사용해야합니다.

// true
[0,1,2].every(v => [0,1,2,3,4,5].includes(v));

//false
[0,1,2].every(v => [0,1,3,4,5, 6].includes(v));

 

팁 2. flatMap에 대해서

const key = relation.flatMap((val) => col.map(item => val[item]).join(""));

flatMap은 배열의 depth를 줄여주는 역할을 해줍니다. 말그대로 평평하게 해주는 map이네요.

이번 분기의 해당 column 값을 relation에서 빼와서 string으로 만들어주기 위해서 사용했습니다.

val = ["100","ryan","music","2"];
col = [0, 1];
// => "100ryan"

 

이번 문제는 뭔가 얻어가는게 많네요.

그럼 이만!