[Programmers] 비밀 코드 해독 - Java

문제

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

프로그래머스

 

풀이

1~n까지의 숫자에서 5개를 뽑아 q배열에 있는 암호코드와 일치하는 수 조합의 개수를 찾는 문제이다.

 

1. 재귀적 가치지기 기법으로 집합을 사용해 5개를 뽑는다.

 

2. 5개를 뽑으면 전체 순회해서, 암호 코드와 일치하는지 확인해서 일치하면 answer를 증가시킨다.

 

가지치기를 이용할 수 있는 이유? 

최대 30까지 수가 나오는데, 5개를 뽑는 것이다.

(30 * 29 * 28 * 27 * 26)/(5 * 4 * 3 * 2 * 1)[30까지의 수에서 5개를 뽑음] * (25)[암호코드에 해당하는지 확인]의 연산이다.

 

이 값들을 근사치로 해서 구해보면, 1억연산이 되지 않는 것을 판단할 수 있다.

소스코드

import java.util.HashSet;

class Solution {
    static int answer;
    
    static int[][] arr;
    static int[] cntArr;
    
    static HashSet<Integer> set;
    
    public int solution(int n, int[][] q, int[] ans) {
        answer = 0;
        
        arr = q;
        cntArr = ans;
        
        set = new HashSet<>();
    
        backTrack(1, n, 5);
        
        return answer;
    }
    
    void backTrack(int num, int n, int r) {
        if (set.size() == r) { 
            if (check()) answer++;
            
            return;
        }
        
        if (num > n) return;
        
        set.add(num);
        backTrack(num + 1, n, r);
        set.remove(num);
        backTrack(num + 1, n, r);
    }
    
    static boolean check() {
        for (int i = 0; i < arr.length; i++) {
            int cnt = 0;
            
            for (int j = 0; j < arr[i].length; j++) {
                if (set.contains(arr[i][j])) {
                    cnt++;
                }
            }
            
            if (cnt != cntArr[i]) {
                return false;
            }
        }
        
        return true;
    }
}

 

실행결과