[프로그래머스 Lv2] 비밀 암호 해독 - Javascript 풀이

https://school.programmers.co.kr/learn/courses/30/lessons/388352?language=javascript

프로그래머스

---

문제

비밀 암호로 가능한 조합의 개수를 찾는 문제

 

생각

1~n까지 숫자 각각 확률을 구해야 하나.. ? 

풀이가 떠오르지 않아서 막막했다.

 

한참 고민하다  결국 구글링을 했다. ( 세상에 천재가 너무 많아 )

아래 블로그 포스팅을 읽었다 !! 

https://j3sung.tistory.com/1246

 

이해력이 문제인지글을 읽어도 이해가 안되서 지피티한테 한번 더 물어봤다.

 

결론 - 이제 완벽히 이해함백트래킹을 통해 모든 조합을 만들고,쿼리와 비교하면서 일치하는 숫자의 개수가 동일한 것만 필터로 걸러주면 된다.

 

문제풀이

백트래킹으로 1~n까지의 서로 다른 정수 5개의 모든 조합을 만든다.

쿼리와 비교하며, 해당 조합이 비밀 암호 후보가 될 수 있는지 체크한다.

 

예시1번에서 q[0]을 예시로 보자.

 

q[0]인 [1, 2, 3, 4, 5]와 조합 [1, 2, 3, 4, 6]는 4개의 숫자가 일치한다. ( 1, 2, 3, 4 ) 

하지만 시스템 응답 개수는 2개이므로 비밀 암호로는 적합하지 않다.

 

q[0]인 [1, 2, 3, 4, 5]와 조합 [4, 5, 6, 7, 8]은 2개의 숫자가 일치한다. ( 4, 5 ) 

시스템 응답 개수가 2개이므로 비밀 암호의 후보로 적합하다.

 

이런식으로 q 배열을 순회하면서 가능한 조합들을 필터해주면

결국 모든 쿼리를 만족하는 조합들만 남게된다.

 

* Set을 사용한 이유는 배열로 풀 경우 indexOf()나 includes() 같은 메서드를 이용해

특정 숫자가 포함되어 있는지 확인할 때 O(n) 시간이 걸리지만,

Set은 내부적으로 해시 구조를 사용해 O(1) 시간에 탐색할 수 있기 때문이다 ! 

 

시간 복잡도는 O(m x C(n x 5)) 이다.

 

q[0]	시스템 응답 개수	조합	일치하는 개수
[1, 2, 3, 4, 5]	2개	[1, 2, 3, 4, 5]	5개
		[1, 2, 3, 4, 6]	4개
		[4, 5, 6, 7, 8]	2개
		[6, 7, 8, 9, 10]	0개

 

코드

// 모든 조합 생성
function getCombination(n) {
    const results = []

    function combination(num, cnt, arr) {
        if ( cnt === 5 ) {
            results.push([...arr])
            return 
        }

        for(let i=num; i<=n; i++) {
            arr.push(i)
            combination(i+1, cnt+1, arr)
            arr.pop()
        }
    }
    
    combination(1, 0, [])
    return results
}

function solution(n, q, ans) {
    let combi = getCombination(n)
    
    q.forEach((query, idx) => {
        const querySet = new Set(query)
        
        combi = combi.filter((arr) => {
            let match = 0
            
            for(let num of arr) {
                if (querySet.has(num)) match++;
            }
            
            return ans[idx] === match
        })
    })
    
    return combi.length  
}

/*
1~n까지의 서로 다른 정수 5개의 모든 조합 만들기 - 백트래킹
만든 조합과 입력한 정수를 비교해서 일치하는 개수가 동일한 경우 - 비밀코드로 가능
*/