[프로그래머스/LV2] 비밀 코드 해독 - 조합(Java)

[2025 프로그래머스 코드챌린지 1차 예선] 비밀 코드 해독](https://school.programmers.co.kr/learn/courses/30/lessons/388352)

🙋‍♂️ 들어가며

문제를 읽어보면 조건은 다음과 같다.

• 가능한 정수 조합은 오름차순 정렬, 중복 불가능
• 1 <= n(가능한 숫자) <= 30
• 1 <= q (입력 숫자들 모음 길이) <= 10
• 1 <= q[i] <= 5

그래서 먼저 든 생각은 조합을 통해 구할 수 있겠다는 생각이 들었으나 java의 경우 1초에 1억 연산이라 시간초과에 위배된다면 조합이 아니라는 뜻이었기에 검증부터 해보았다.

먼저 오름차순 정렬이고, 중복이 불가능하기에 1 2 3 4 5는 되고 3 1 4 2 5는 되지 않는다

그래서 P가 아닌 C로 $\binom{30}{5}$ 경우가 되겠다.

그리고 q의 길이 10, q[i]의 길이 5

그리고 테스트케이스에서 만약 임의의 조합이 3 4 7 9 10 일때, 첫째 입력숫자가 1 2 3 4 5 일때

cnt = 2 이기에, 임의의조합을 위한 1개의 반복문이 더 필요했었다.

그래서 최종적으로 나는 최악의 연산수행을 다음과 같이 결론 지었다

$\binom{30}{5}$ * 10 * 5 * 5

약 3560만, 충분히 1초안에 통과 가능한 숫자다.

자연어로 사고의 흐름을 작성해보면 다음과 같다.

// 1. Solution 함수
    // 1-1. 1중 for문을 통해 첫번째 조합생성기를 통한 탐색 시작


// 2. 함수 (조합 생성기)
    // 2-1. idx == 5 일때
        // 2-1-a. 함수 (전부 유효한가? == true) -> true
        // 2-1-b. 검사 종료후 return

    // 2-2. 가지치기 -> (만약 불가능한 조합일 때)

    // 2-3. 그 외는 계속 탐색


// 3. 함수 (전부 유효한가?)
    // 3-1. 하나라도 req_cnt와 안맞다면 false
    // 3-2. 전부 살아남았다면 true

참 가지치기가 왜 생각났냐면 예를들어 my_comb = {26, 0, 0, 0, 0} 일 때

idx=1, 그리고 4칸을 더 채울 수 있다. -> 27, 28, 29, 30

그래서 만약 현재 숫자 + 끝 idx - 현재 idx > 30 이라면 다 못채운다는 뜻이다

계산을 해보면 27 + 4 - 1이라 충분히 30보다 큰게 아니라서 충분히 가능

여기서 생각을 해보자

만약 my_comb = {28, 0, 0, 0, 0} 일때

idx = 1, 그리고 2칸을 더채울 수 있다 29, 30 을 말이다.

그러면 29 + 4 - 1 -> 당연히 30이 넘으니 볼 필요도 없어서 return false

✅ 코드 (조합)

class Solution {
    static int answer = 0;
    
    
    public int solution(int n, int[][] q, int[] ans) {
        // 오름차순 정렬이기에 위치가 다른 중복이 불가능이라 P가 아니라 C
        // 그래서 최악의 연산 (30C5 * 10 * 5 * 5) -> 약 3560만 (충분히 1억 연산 이내 통과)
        
        
        // 1. 조합 생성기 작동시작
        boolean[] visited = new boolean[n+1];
        int[] my_comb = new int[5];
        int idx = 0;
        for (int i = 1; i < n+1; i++) {
            int num = i;
            visited[idx] = true;
            my_comb[idx] = num;
            comb_maker(num+1, idx+1, my_comb, visited, n, q, ans);
            visited[idx] = false;
        }
        
        // 2. 가능한 조합의 갯수 반환
        return answer;
    }
    
    
    
    // 3. 함수 (조합 생성기)
    static void comb_maker(int num, int idx, int[] my_comb, boolean[] visited, int n, int[][] q, int[] ans) {
        
        // 3-1. 임의의 조합에 숫자 5개 다 채웠다면?
        if (idx == 5) {
            // 3-1-a. 가능한 조합이면 answer++
            if (is_valid(my_comb, q, ans)) {
                answer++;
            }
            // 3-1-b. 검사후 종료
            return;
        }
        
        // 3-2. 가지치기 (불가능한 조합일떄)
        if (num + 4 - idx > n) return;
        
        // 3-3. 그외는 조합 생성
        for (int next_num = num; next_num < n+1; next_num++) {
            visited[next_num] = true;
            my_comb[idx] = next_num;
            comb_maker(next_num+1, idx+1, my_comb, visited, n, q, ans);
            visited[next_num] = false;
        }
    }
    
    
    
    
    // 4. 함수 (가능한 조합인지 검사)
    static boolean is_valid(int[] my_comb, int[][] q, int[] ans) {
        int row = q.length;
        int col = q[0].length;
        for (int r = 0; r < row; r++) {
            int req_cnt = ans[r];
            int cnt = 0;
            
            // 4-1. 입력한 정수들과 내 조합 각각 비교 
            for (int c = 0; c < col; c++) {
                for (int k = 0; k < my_comb.length; k++) {
                    if (q[r][c] == my_comb[k]) cnt++;
                }
            }
            // 4-2. 만약 필요한 암호횟수와 나의 암호갯수가 일치안하면 -> false
            if (req_cnt != cnt) return false;
        }
        
        // 4-3. 필요한 암호횟수와 나의 암호갯수가 전부 일치시 -> true
        return true; 
    }
    
    
}