[JS] 후보키

문제의 조건을 조금 헷갈려서 많이 헤맨 문제였다.

 

 

 

처음에는 조합을 활용해서 1개짜리,2개짜리,3개짜리 ,,, 이런식으로 후보키를 찾아 나가되 

 

 

 

최소성을 깨지 않기 위해서 한번 후보키가 된 경우는 삭제해야 한다고 생각했다.

 

 

 

 

[["a", "1", "aaa", "c", "ng"], ["b", "1", "bbb", "c", "g"], ["c", "1", "aaa", "d", "ng"], ["d", "2", "bbb", "d", "ng"]]

 

 

그런데 위와같은 경우를 보자.

해당 경우의 후보키는

 

[0] , [2,3] , [1,3,4] 이렇게 3개가 나온다.

 

 

즉 , 3번이 [2,3] 한번의 쌍으로 들어가긴 했지만 [1,3,4]로 후보키가 이뤄질 수 있기때문에 한번 후보키가 된경우에서는 빼면 안된다.

 

 

 

후보키가 완성되었다면, 그 후보키 자체를 하나로 봐야한다. [1,3,4]가 후보키가 될 수 있는 이유는 [2,3] 을 전부 포함하고 있지 않기 때문이다.

 

 

위 문제를 해결했는데도 몇몇 테스트케이스가 해결되지 않았다. 그이유는 다음과 같다.

 

 

[["a", "aa"], ["aa", "a"], ["a", "a"]]

 

 

필자는 문제를 풀면서 키들을 합칠때 단순하게 문자열을 이어 붙였는데 위와같이 문자열을 이어 붙이면 키가 다름에도 결과가 똑같이 나와 set 처리를 했을때 사라지는경우가 존재했다.

 

문제에서 알파벳 소문자와 숫자만 들어온다고되어있어 2가지 이상 키를 합치는 경우 스페이스를 넣어서 합쳐줌으로 해당 문제를 해결했다.

 

 

 

 

 

따라서 문제를 해결하는 방법을 정리하자면 아래와 같다.

 

1. 후보키를 만들기 편하게 들어온 2차원 배열을 전치시킨다.

2. 1개 ~ n(배열의 크기)개까지 조사한다.

3. 모든 경우의수를조합으로 나타낸다.

4. 각 경우의수를 더해준 하나의 문자키를 만들어준다.

5. set자료형을 활용해 유일성이 성립하는지 체크한다.

6. 유일성이 성립되었다면 최소성을 확인해준다.

7. 유일성과 최소성이 모두 성립되었다면 정답 배열에 추가해준다.

8. 배열의 크기를 반환해준다.

 

 

 

 

 

 

 

 

 

const getCombination = (ary,n) => {
    let ret = []
    if (n===1) return ary.map(v => [v])
    
    ary.forEach((fixed,idx,ori) => {
        const rest = ori.slice(idx+1)
        const combinations = getCombination(rest,n-1)
        const attached = combinations.map(v => [fixed,...v])
        
        ret.push(...attached)
    })
    return ret
}


function solution(relation) {
    relation = relation.reduce((result, row) => row.map((_, i) => [...(result[i] || []), row[i]]),[]);
    
    let ret = []
    
    for (let i = 1 ; i <= relation.length ; i++) {
        const comAry = getCombination(relation,i)
        
        for (const ary of comAry) {
            
            let newAry = new Array(ary[0].length).fill("")
            for (let j = 0 ; j < ary.length ; j++){
                for (let k = 0 ; k < ary[0].length ; k++) {
                    newAry[k] += " " + ary[j][k]
                }
            }
            
            const set = new Set(newAry)
            if(set.size === newAry.length) {
                const idxAry = ary.map(v => relation.indexOf(v))
                if(!ret.some(v => v.every(el => idxAry.includes(el)))){
                    ret.push(idxAry)
                }
            }
        }
    }
    
    return ret.length
}