[개발일지] - 30(주말)

(1).백준 20529번 가장 가까운 세 사람의 심리적 거리는 참여자의 MBTI를 비교해 

각각 하나가 불일치할 때마다 1씩 거리가 증가하는 구조로

a, b, c의 세사람의 거리를 구할 경우 a, b / b, c / a, c의 세개의 거리를 모두 합한 총 합을 말한다.

 

처음에는 가장 가까운 세 사람이라는 말에 현혹되어 a,b,c,d,e,f,g의 경우 a,b,c / b,c,d/ c,d,e 순서로 구한다고 생각하고

문제를 해결했으며 테스트케이스도 하필 그 테스트로 통과가 되서 문제가 없었지만

25%정도에서 오답으로 틀려버려서 문제를 확인할 수 있었다.

 

하지만 조합으로 넘어가게 되면 너무 큰 숫자가 되어버려서 시간복잡도에 걸릴 수 밖에 없는데

이 부분에서 문제 태그에 왜 비둘기집이라고 써져있는지를 이해할 수 있었다.

 

숫자가 얼마나 많은지는 신경쓸 필요 없고

오히려 경우의 수가 16이기 때문에 16 + 16 + @가 되는 순간 동일한 MBTI가 하나 이상 있다는 보장이 되기 때문에

간단히 0을 출력하면 되는 것이었고

그 이하의 경우에는 단순 조합을 통해 문제를 해결할 수 있었다.

const input = `3
3
ENTJ INTP ESFJ
4
ESFP ESFP ESFP ESFP
5
INFP INFP ESTP ESTJ ISTJ `.split('\n')

const result = []
const checker = (a,b,c) => {
    let sum = 0
    for(let i = 0 ; i < 4 ; i++){
        if(a[i] !== b[i]){
            sum += 1
        }
        if(a[i] !== c[i]){
            sum += 1
        }
        if(b[i] !== c[i]){
            sum += 1
        }
    }
    return sum
}

for(let i = 2 ; i < input.length ; i+=2){
    const test = input[i].split(' ')
    let min = 16
    if(test.length > 32){
        result.push(0)
        continue
    }
    for(let j = 0 ; j < test.length-2 ; j++){
        for(let k = j+1 ; k < test.length-1 ; k++){
            for(let l = k+1 ; l < test.length ; l++){
                min = Math.min(min, checker(test[j], test[k], test[l]))
            }
        }
    }
    result.push(min)
}

console.log(result.join('\n'))