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

 

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

프로그래머스

 

---

 

문제 개요

비밀 조직의 보안 시스템을 해독하기 위해, 1부터 nnn까지의 숫자 중 서로 다른 5개 숫자로 이루어진 비밀 코드를 찾아야 합니다. m번의 시도를 할 수 있으며, 각 시도마다 입력한 5개의 숫자와 비밀 코드 간의 일치하는 숫자의 개수를 확인할 수 있습니다. 주어진 m번의 시도 결과를 바탕으로, 가능한 비밀 코드 조합의 개수를 구하는 문제입니다.

 

 

문제 접근 방법

1. 모든 가능한 5개 숫자의 조합을 생성
   • 1부터 n까지의 숫자 중 5개를 선택하는 조합을 만듬
2. 각 조합이 주어진 시도 결과와 일치하는지 검사한다.
   • 주어진 각 시도 q[i]에 대해 비밀 코드와의 교집합 크기를 계산
   • 이 값이 시스템 응답 ans[i]와 일치하는지 확인
   • 모든 시도에 대해 조건을 만족하는 경우, 해당 조합을 유효한 비밀 코드 후보로 등록
3. 유효한 조합의 개수를 세어 반환한다.

 

 

코드

import java.util.*;
class Solution {
    static int answer = 0;
    static int[] arr;
    public int solution(int n, int[][] q, int[] ans) {        
        arr = new int[n];
        for(int i=0; i<n; i++) arr[i] = i+1;
        comb(n, q, ans, 0, new ArrayList<>());
        return answer;
    }
    
    public void comb(int n, int[][] q, int[] ans, int cur, List<Integer> list) {
        if(list.size() == 5) {
            // System.out.println(list);
            if(isPossible(q, ans, list)) answer++;
            return;
        }
        
        for(int i=cur; i<n; i++) {
            list.add(arr[i]);
            comb(n, q, ans, i+1, list);
            list.remove(list.size() - 1);
        }
    }
    
    public boolean isPossible(int[][] q, int[] ans, List<Integer> list) {
        for(int i=0; i<q.length; i++) {
            int cnt = 0;
            for(int j=0; j<q[i].length; j++) {
                for(int k=0; k<list.size(); k++) {
                    if(q[i][j] == list.get(k)){
                        cnt++;
                        break;
                    }
                }
            }
            
            if(cnt != ans[i]) return false;
        }
        return true;
    }
}