[프로그래머스] 비밀 코드 해독

https://school.programmers.co.kr/learn/courses/30/lessons/388352

프로그래머스

제한사항

10 ≤ n ≤ 30

1 ≤ (q의 길이 = m) ≤ 10
q[i]의 길이 = 5q[i]는 i+1번째 시도에서 입력한 5개의 서로 다른 정수를 담고 있으며, 오름차순으로 정렬되어 있습니다.
1 ≤ q[i][j] ≤ n

ans의 길이 = m
ans[i]는 i+1번째 시도에서 입력한 5개의 정수 중 비밀 코드에 포함된 정수의 개수를 나타냅니다.
0 ≤ ans[i] ≤ 5

비밀 코드가 존재하지 않는(답이 0인) 경우는 주어지지 않습니다.

 

처음 문제를 보고 접근했을 때 제한사항에 나와있는 수가 그렇게 크지 않고 최악을 구해보아도 크지 않음을 알 수 있었음

 

다만, 브루트포스 말고 다른 방법을 찾아봤지만 떠오르지 않았음 그래서 생각하던 중 dfs와 유사하게 풀이하는 방식 채택

 

수 조합을 만들어야 하기 때문에 방문한 수는 방문처리를 해주고 모든 경우의 수를 찾아야 하기 때문에 전체 탐색을 할 수 있도록 구현함

 

정답을 유추했을 때 정답에 120을 곱한 값이 나왔는데 모든 경우의 수를 탐색하다 보니 발생한 문제였음 그래서 다음 스텝으로 넘어갈 때 이전의 값보다 작은 값은 넘어가도록 구현

 

문제를 어렵게 생각하는 것보다 어떻게 하면 간단하게 풀 수 있을지 연습해야 함

function solution(n, q, ans) {
    var answer = 0;
    
    const visited = Array(n + 1).fill(false)
        
    const dfs = (set) => {
        if(set.length == 5){
            let flag = true;
            for(let i = 0; i < q.length; i++){
                const sameCnt = set.filter(it => q[i].includes(it)).length;
                if(sameCnt != ans[i]) {
                    flag = false;
                    break;
                }
            }
            
            if(flag) {
                answer++;
            }
            return;
        }
        
        for(let i = 1; i <= n; i++){
            if(visited[i]) continue;
            if(set[set.length - 1] > i) continue;
            
            visited[i] = true;
            dfs([...set, i]);
            visited[i] = false;
        }
    }
    
    dfs([]);
    
    return answer;
}