[KAKAO RECRUITMENT] 후보키 풀이 / JavaScript

프로그래머스

 

 

작성 코드 (1차 시도 / 통과)

function solution(relation) {
    const getCombinations = (arr, num) => { // 조합 구하기
        const combs = [];
        if (num === 1) return arr.map(v => [v]);
        arr.forEach((fixed, index, origin) => {
            const rest = origin.slice(index + 1);
            const combinations = getCombinations(rest, num - 1);
            const attached = combinations.map(v => [fixed, ...v]);
            combs.push(...attached);
        });
        return combs;
    }
    
    let result = 0
    let table = Array.from({length: relation[0].length}, () => [])
    
    // 각 튜플의 속성을 컬럼 배열로 구분
    relation.forEach(r => { 
        for (let ri = 0; ri < r.length; ri += 1) table[ri].push(r[ri])
    })
    // 슈퍼키 제거
    for (let ti = 0; ti < table.length; ti += 1) {
        if (table[ti].length === new Set(table[ti]).size) {
            result += 1
            delete table[ti]
        }
    }
    table = table.filter(t => t)
    if (table.length <= 1) return result
    // 후보키 배열
    const candidate = []
    const tIdx = table.map((t, i) => i)
    for (let i = 2; i <= table.length; i += 1) {
        const combinations = getCombinations(tIdx, i) // 후보키 대상이 될 컬럼 인덱스 조합
        for (const comb of combinations) { 
            let next = false
            // 현재 조합이 이미 후보키에 포함되어있으면(== 최소성을 만족하지 않으면) skip
            for (const cand of candidate) if (cand.every(v => comb.includes(v))) next = true
            if (next) continue
            
            // 컬럼 조합 생성
            const combCheck = []
            for (let j = 0; j < relation.length; j += 1) {
                let combined = ""
                comb.forEach(c => combined += table[c][j])
                combCheck.push(combined)
            }
            if (combCheck.length === new Set(combCheck).size) { // 유일성을 만족하면 후보키에 등록
                result += 1
                candidate.push(comb)
            }
        }
    }
    return result
}

 

구현 로직 (조합 사용)

유일성, 최소성에 대한 이해가 필요합니다. 유일성을 찾기는 쉽지만 최소성을 가려내는 것이 문제 구현의 핵심입니다.

 

1. relation 배열의 각 튜플을 컬럼으로 구분하여 배열 생성

2. 슈퍼키 제거(슈퍼키가 조합으로 들어가면 최소성에 어긋납니다)

3. 후보키를 만들기 위한 대상 컬럼들(table)의 인덱스를 배열로 생성(이 배열로 조합 구성합니다)

4. 2개부터 시작하여 table의 길이까지 순차적으로 조합.

  4-1. 현재 순회중인 조합이 이미 후보키에 포함되어 있으면(=최소성을 만족하지 않으면) 생략

5. 후보키에 포함되어있지 않으면 조합에 들어있는 각 인덱스에 해당하는 컬럼을 조합. 예를 들어 조합할 인덱스가 [0, 1] 이고 table이 [["ryan", "apeach", "tube"], ["music", "math", "computer"], ["2", "2", "3"]] 이라면 조합된 컬럼은 ["ryanmusic", "apeachmath", "tubecomputer"] 가 됩니다.

  5-1. 이 조합이 유일성을 만족하면 후보키에 등록.

6. 카운트된 후보키 개수(result) 출력