[Programmers Lv.2 | JS] 후보키

프로그래머스 후보키 문제 링크

풀이

혼자서 문제를 어떻게 해서든 풀어보려고 했는데..
도저히 해결이 되지 않아 다른 분들의 풀이를 따라가며 문제를 풀었습니다.
다른 분들 풀이도 한 눈에 이해하지 못해서 굉장히 헤맸습니다.

일단, 풀이는 다음과 같습니다.

// 조합을 반환
const getCombinations = (arr, length) => {
    if (length === 1) return arr.map((value) => [value]);
    
    const result = arr.reduce((acc, cur, index, origin) => {
        const rest = origin.slice(index + 1);
        const combinations = getCombinations(rest, length - 1);
        const attached = combinations.map(combination => [cur, ...combination]);
        
        acc.push(...attached);
        return acc;
    }, []);
    
    return result;
}

// 조합에 따른 문자열 키 반환
const getKeys = (combination) => {
    // 문자열 키를 만들기 위해 배열을 빈 문자열로 초기화
    let keys = Array.from({ length: combination[0].length }, () => '');

    // 각 조합에 따른 문자열 키를 생성
    for (let i = 0; i < combination.length; i++) {
        for (let j = 0; j < combination[0].length; j++) {
            keys[j] += combination[i][j];
        }
    }
    
    return keys;
}

// 유일성 확인
const isUniqueness = (combination, relation) => {
    const keys = getKeys(combination);
    const keysSet = new Set(keys);

    return keysSet.size === relation.length;
}

function solution(relation) {
    let candidateKeys = [];
    // relation의 행과 열의 위치를 변경, 열을 기준으로 하는 2차원 배열 
    const columns = relation.reduce((acc, cur) => {
        return cur.map((_, index) => [...(acc[index] || []), cur[index]])
    }, []);

    // columns의 길이만큼 순회
    for (let i = 1; i <= columns.length; i++) {
        // columns에 대한 조합
        const combinations = getCombinations(columns, i);;
        // 각 조합을 순회하면서
        combinations.forEach((combination, index) => {
            // 유일성 체크
            if (isUniqueness(combination, relation)) {
                // 유일성을 통과한 조합을 인덱스 값으로 변경
                const indicesOfCombination = combination.map(value => columns.indexOf(value));
                // 최소성을 만족하기 위해 후보키에 저장 여부 확인
                const isMinimality = !candidateKeys.some(value => {
                    return value.every(element => indicesOfCombination.includes(element))
                });
                
                // 최소성 체크
                if(isMinimality) {
                    // 최소성을 만족한다면 후보키에 저장
                    candidateKeys.push(indicesOfCombination);
                }
            }
        })
    }

    // 후보키의 길이를 반환
    return candidateKeys.length;
}

설명

문제를 다음과 같은 순서대로 풀이했습니다.

조합 구하기

먼저, 각 컬럼에 대한 조합을 구합니다.
컬럼에 대한 조합을 구하기 위해 열 기준의 릴레이션을 컬럼 기준의 2차원 배열로 변경했습니다.

const columns = relation.reduce((acc, cur) => {
    return cur.map((_, index) => [...(acc[index] || []), cur[index]])
}, []);

columns는 다음과 같은 형태입니다.

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

# 위의 relation을 다음의 columns로 변경
# columns
> [
  [ '100', '200', '300', '400', '500', '600' ],
  [ 'ryan', 'apeach', 'tube', 'con', 'muzi', 'apeach' ],
  [ 'music', 'math', 'computer', 'computer', 'music', 'music' ],
  [ '2', '2', '3', '4', '3', '2' ]
]

그리고 columns를 순회하면서 조합을 구합니다.
조합에 대한 설명은 링크를 참고해주세요.

// columns의 길이만큼 순회
for (let i = 1; i <= columns.length; i++) {
    // 열 기준으로 조합을 구함
    const combinations = getCombinations(columns, i);;
    ...
}

for 문 내에서 combinations를 출력하면 다음과 같은 형태입니다.

# combinations
# length = 1 
> [
  [ [ '100', '200', '300', '400', '500', '600' ] ],
  [ [ 'ryan', 'apeach', 'tube', 'con', 'muzi', 'apeach' ] ],
  [ [ 'music', 'math', 'computer', 'computer', 'music', 'music' ] ],
  [ [ '2', '2', '3', '4', '3', '2' ] ]
]
# length = 2 
> [
  [
    [ '100', '200', '300', '400', '500', '600' ],
    [ 'ryan', 'apeach', 'tube', 'con', 'muzi', 'apeach' ]
  ],
  [
    [ '100', '200', '300', '400', '500', '600' ],
    [ 'music', 'math', 'computer', 'computer', 'music', 'music' ]
  ],
  [
    [ '100', '200', '300', '400', '500', '600' ],
    [ '2', '2', '3', '4', '3', '2' ]
  ],
  [
    [ 'ryan', 'apeach', 'tube', 'con', 'muzi', 'apeach' ],
    [ 'music', 'math', 'computer', 'computer', 'music', 'music' ]
  ],
  [
    [ 'ryan', 'apeach', 'tube', 'con', 'muzi', 'apeach' ],
    [ '2', '2', '3', '4', '3', '2' ]
  ],
  [
    [ 'music', 'math', 'computer', 'computer', 'music', 'music' ],
    [ '2', '2', '3', '4', '3', '2' ]
  ]
]
# length = 3 
> [
  [
    [ '100', '200', '300', '400', '500', '600' ],
    [ 'ryan', 'apeach', 'tube', 'con', 'muzi', 'apeach' ],
    [ 'music', 'math', 'computer', 'computer', 'music', 'music' ]
  ],
  [
    [ '100', '200', '300', '400', '500', '600' ],
    [ 'ryan', 'apeach', 'tube', 'con', 'muzi', 'apeach' ],
    [ '2', '2', '3', '4', '3', '2' ]
  ],
  [
    [ '100', '200', '300', '400', '500', '600' ],
    [ 'music', 'math', 'computer', 'computer', 'music', 'music' ],
    [ '2', '2', '3', '4', '3', '2' ]
  ],
  [
    [ 'ryan', 'apeach', 'tube', 'con', 'muzi', 'apeach' ],
    [ 'music', 'math', 'computer', 'computer', 'music', 'music' ],
    [ '2', '2', '3', '4', '3', '2' ]
  ]
]
# length = 4 
> [
  [
    [ '100', '200', '300', '400', '500', '600' ],
    [ 'ryan', 'apeach', 'tube', 'con', 'muzi', 'apeach' ],
    [ 'music', 'math', 'computer', 'computer', 'music', 'music' ],
    [ '2', '2', '3', '4', '3', '2' ]
  ]
]

유일성 확인하기

생성된 조합을 순회하면서 유일성을 확인합니다.

유일성(uniqueness)

릴레이션에 있는 모든 튜플에 대해 유일하게 식별되어야 한다.

유일성을 확인하기 위해 각 조합을 하나의 문자열 키로 생성했습니다.

// 조합에 따른 문자열 키 반환
const getKeys = (combination) => {
    // 문자열 키 배열을 만들기 위해 빈 문자열로 초기화
    let keys = Array.from({ length: combination[0].length }, () => '');

    // 각 조합에 따른 문자열 키를 생성
    for (let i = 0; i < combination.length; i++) {
        for (let j = 0; j < combination[0].length; j++) {
            keys[j] += combination[i][j];
        }
    }

    return keys;
}

keys는 다음과 같은 형태로 생성됩니다.

# key
# length = 1
> [ '100', '200', '300', '400', '500', '600' ]
> [ 'ryan', 'apeach', 'tube', 'con', 'muzi', 'apeach' ]
> [ 'music', 'math', 'computer', 'computer', 'music', 'music' ]
> [ '2', '2', '3', '4', '3', '2' ]

# length = 2
> [ '100ryan', '200apeach', '300tube', '400con', '500muzi', '600apeach' ]
> [
  '100music',
  '200math',
  '300computer',
  '400computer',
  '500music',
  '600music'
]
> [ '1002', '2002', '3003', '4004', '5003', '6002' ]
> [
  'ryanmusic',
  'apeachmath',
  'tubecomputer',
  'concomputer',
  'muzimusic',
  'apeachmusic'
]
> [ 'ryan2', 'apeach2', 'tube3', 'con4', 'muzi3', 'apeach2' ]
> [ 'music2', 'math2', 'computer3', 'computer4', 'music3', 'music2' ]

# length = 3
> [
  '100ryanmusic',
  '200apeachmath',
  '300tubecomputer',
  '400concomputer',
  '500muzimusic',
  '600apeachmusic'
]
> [
  '100ryan2',
  '200apeach2',
  '300tube3',
  '400con4',
  '500muzi3',
  '600apeach2'
]
> [
  '100music2',
  '200math2',
  '300computer3',
  '400computer4',
  '500music3',
  '600music2'
]
> [
  'ryanmusic2',
  'apeachmath2',
  'tubecomputer3',
  'concomputer4',
  'muzimusic3',
  'apeachmusic2'
]

# length = 4
> [
  '100ryanmusic2',
  '200apeachmath2',
  '300tubecomputer3',
  '400concomputer4',
  '500muzimusic3',
  '600apeachmusic2'
]

유일성을 확인합니다.

// 유일성 여부를 불리언 값으로 반환
const isUniqueness = (combination, relation) => {
    // 조합에 따른 문자열 키 생성
    const keys = getKeys(combination);
    // set 자료 구조를 이용하여 중복된 문자열 키를 삭제
    const keysSet = new Set(keys);

    // keysSet의 크기와 릴레이션의 길이를 비교하여 유일성을 판단
    return keysSet.size === relation.length;
}

최소성 확인하기

유일성을 만족한다면 최소성을 확인합니다.

최소성(minimality)

유일성을 가진 키를 구성하는 속성(Attribute) 중 하나라도 제외하는 경우 유일성이 깨지는 것을 의미한다. 즉, 릴레이션의 모든 튜플을 유일하게 식별하는 데 꼭 필요한 속성들로만 구성되어야 한다.

최소성을 확인하기 위해 유일성을 만족하는 조합을 인덱스 값으로 변환합니다.

const indicesOfCombination = combination.map(value => columns.indexOf(value));

# 유일성을 만족하는 combination
> [ [ '100', '200', '300', '400', '500', '600' ] ]
> [
  [ '100', '200', '300', '400', '500', '600' ],
  [ 'ryan', 'apeach', 'tube', 'con', 'muzi', 'apeach' ]
]
> [
  [ '100', '200', '300', '400', '500', '600' ],
  [ 'music', 'math', 'computer', 'computer', 'music', 'music' ]
]
> [
  [ '100', '200', '300', '400', '500', '600' ],
  [ '2', '2', '3', '4', '3', '2' ]
]
> [
  [ 'ryan', 'apeach', 'tube', 'con', 'muzi', 'apeach' ],
  [ 'music', 'math', 'computer', 'computer', 'music', 'music' ]
]
v[
  [ '100', '200', '300', '400', '500', '600' ],
  [ 'ryan', 'apeach', 'tube', 'con', 'muzi', 'apeach' ],
  [ 'music', 'math', 'computer', 'computer', 'music', 'music' ]
]
> [
  [ '100', '200', '300', '400', '500', '600' ],
  [ 'ryan', 'apeach', 'tube', 'con', 'muzi', 'apeach' ],
  [ '2', '2', '3', '4', '3', '2' ]
]
> [
  [ '100', '200', '300', '400', '500', '600' ],
  [ 'music', 'math', 'computer', 'computer', 'music', 'music' ],
  [ '2', '2', '3', '4', '3', '2' ]
]
> [
  [ 'ryan', 'apeach', 'tube', 'con', 'muzi', 'apeach' ],
  [ 'music', 'math', 'computer', 'computer', 'music', 'music' ],
  [ '2', '2', '3', '4', '3', '2' ]
]
> [
  [ '100', '200', '300', '400', '500', '600' ],
  [ 'ryan', 'apeach', 'tube', 'con', 'muzi', 'apeach' ],
  [ 'music', 'math', 'computer', 'computer', 'music', 'music' ],
  [ '2', '2', '3', '4', '3', '2' ]
]

# 위의 combination을 인덱스로 변경
> [ 0 ]
> [ 0, 1 ]
> [ 0, 2 ]
> [ 0, 3 ]
> [ 1, 2 ]
> [ 0, 1, 2 ]
> [ 0, 1, 3 ]
> [ 0, 2, 3 ]
> [ 1, 2, 3 ]
> [ 0, 1, 2, 3 ]

최소성을 만족하는지 확인하고 최소성을 만족한다면 후보키에 저장합니다.

const isMinimality = !candidateKeys.some(value => {
    return value.every(element => indicesOfCombination.includes(element))
});

// 최소성 체크
if(isMinimality) {
    // 최소성을 만족한다면 후보키에 저장
    candidateKeys.push(indicesOfCombination);
}

저장된 후보키를 출력하면 다음과 같은 형태입니다.

# candidateKeys
> [ [ 0 ], [ 1, 2 ] ]

최종으로 candidateKeys의 길이를 답으로 반환합니다.

마무리

• 카카오 문제는 풀면 풀수록 어렵네요..
• 다른 분들의 풀이를 참고했지만 제가 이해하기 쉬운 방법으로 코드를 조금 변경해보았습니다.
• 이 글을 보는 다른 분들에게 도움이 되었으면 하네요:)

참고

• [JS] 후보키