[21/09/13 KATA NINJA] 튜플 & 후보키

튜플

풀이

• {} -> []로 바꾸고 JSON parse를 이용하여 배열 리터럴로 만든다. => 길이가 짧은 것부터 순회하기위해 소팅을 해주고 -> 요소들을 순회하며 요소들의 원소가 결과배열에 없다면 추가해준다.

소팅을 해줌으로 써 -> n^2 번 돌아야 하는 문제를 해결

function solution(s){
    let answer = [];
    const array = JSON.parse(s.replace(/[{}]/gi,(char)=>{
        if(char === '{') return '['
        if(char === '}') return ']'
    }))
    array.sort((a,b)=>a.length - b.length)
    
    array.forEach(item =>{
        item.forEach(i =>{
            if(!answer.includes(i)) answer.push(i);
        })
    })
   return answer;
}

다른 풀이

set 자료구조를 이용한 풀이, 결과배열에 포함되었는지 확인하는 로직을 포함하지 않아도 된다.

function solution(s){
    let answer = [];
    const array = JSON.parse(s.replace(/[{}]/gi,(char)=>{
        if(char === '{') return '['
        if(char === '}') return ']'
    }))
    array.sort((a,b)=>a.length - b.length)
    
    array.forEach(element=>{
        answer = [...new Set([...answer,...element])]
    })
    return answer;
}

속도가 단축되었다. (평균적으로) 결과배열에 포함되었는지를 점검하는 로직이 빠져서 그러한듯하다.

후보키

풀이

function getCombination(array){
    const result = [];
    function DFS(n,r,current){
        if(n.length === r){
            result.push(n);
            return ;
        }
        for(let i=current+1;i<array.length;i++){
            DFS([...n,array[i]],r,i);
        }
       
    }
    for(let i=0;i<array.length;i++){
        // 4c1 4c2 4c3 4c4
        
        DFS([],i+1,-1);
    }
    return result;
}
function isOnly(key,object,row){
    const answer = [...new Array(row)].map((r,idx)=>{
        return key.map(k=>object[k][idx]).join('');
    })
    return [...new Set(answer)].length === row;
}
function isMinity(key,object,row){
    const combinations = getCombination(key);
    return combinations.length - 1 === combinations.filter(c=>!isOnly(c,object,row)).length;
}
function solution(relation){
    let answer = 0;
    const object = {};
    relation.forEach(row=>{

        row.forEach((column,idx)=>{
            object[idx] = object[idx] ? [...object[idx],column]:[column];
        })
    })
    const combinations = getCombination(Object.keys(object));
    combinations.forEach(key=>{
        if(isOnly(key,object,relation.length) && isMinity(key,object,relation.length)){
            answer++;
        }
    })
    
    return answer;
}

다른 풀이

• 비트마스크로 풀어보기