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

비밀 코드 해독 (Lv2)

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

코딩테스트 연습 - 비밀 코드 해독

 

 

 

 

제한 사항

• 10 ≤ n ≤ 30
• 1 ≤ (q의 길이 = m) ≤ 10
  • q[i]의 길이 = 5
  • q[i]는 i+1번째 시도에서 입력한 5개의 서로 다른 정수를 담고 있으며, 오름차순으로 정렬되어 있습니다.
  • 1 ≤ q[i][j] ≤ n
• ans의 길이 = m
  • ans[i]는 i+1번째 시도에서 입력한 5개의 정수 중 비밀 코드에 포함된 정수의 개수를 나타냅니다.
  • 0 ≤ ans[i] ≤ 5
• 비밀 코드가 존재하지 않는(답이 0인) 경우는 주어지지 않습니다.

 

 

풀이

이번 문제는 조합을 이용해서 풀었다.

 

먼저 문제에서 비밀코드는 5자리라고 했으므로 1부터 n까지 숫자 중 5개를 조합해서 만든다.
이는 n이 최대 30인 경우에도 142506번 밖에 걸리지 않는다.

다음으로 만들어진 조합이 정답이라고 가정한 후 q 배열 전부와 비교를 한다.
이때, q 배열과 일치하는 것이 x개인데 ans[q인덱스]가 y개(x!=y)라면 맞지 않는 것이다.
예를 들어, 조합이 [1,2,3,4,5], q[0] = [1,2,3,4,6], ans[qIdx] = 3인 경우에, 조합이 정답이라고 가정했기에 q[0]과의 교집합은 4가 나와야 한다. 하지만 ans[qIdx] = 3이므로 [1,2,3,4,5]는 정답이 될 수 없다.

이처럼 모든 조합에 대해 비교한 후, 모든 조건에 부합한다면 answer를 하나 늘려 정답을 구했다.

 

 

 

전체 Code

class Solution {
    int[] sub;
    int answer;
    public int solution(int n, int[][] q, int[] ans) {
        answer = 0;
        sub = new int[5];
        comb(0,1,n,q,ans);
        return answer;
    }
    
    private void comb(int idx, int num, int n, int[][] q, int[] ans){
        if(idx==5){
            if(calculate(q,ans)) answer++;
            return;
        }
        for(int i=num; i<=n; i++){
            sub[idx] = i;
            comb(idx+1, i+1, n, q, ans);
        }
    }
    
    private boolean calculate(int[][] q, int[] ans){
        int[] subCnt = new int[31];
        for(int s : sub){
            subCnt[s]++;
        }
        for(int i=0; i<q.length; i++){
            int cnt = 0;
            // q를 순회하면서 같은게 몇개 있는지 판별
            for(int j=0; j<q[i].length; j++){
                if(subCnt[q[i][j]]==1) cnt++;
            }
            // 같은게 3개다. 근데 ans는 2개다? 같은게 2개다. 근데 ans는 3개다? 다 말이 안된다.
            if(cnt != ans[i]) return false;
        }
        return true;
    }
}