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

문제 개요

사용자가 1부터 $n$ 사이의 서로 다른 정수 5개를 골라 비밀 코드를 만듭니다.
우리는 몇 번의 시도($q$)와 그 시도에서 맞춘 숫자의 개수($ans$)를 토대로, 가능한 비밀 코드의 총 개수를 구해야 합니다.

제약 사항: $n$은 최대 30, 시도 횟수는 최대 10회
핵심: 가능한 모든 조합을 탐색하되, 주어지는 힌트를 이용해 탐색 범위를 얼마나 효율적으로 줄이느냐가 관건입니다.

접근 방법

효율적인 백트래킹(Backtracking)단순히 모든 조합($_{n}C_{5}$)을 구하고 나중에 검증하는 방식은 $n=30$일 때 약 14만 개의 조합을 생성해야 하므로 비효율적일 수 있습니다.

이번 풀이에서는 재귀 호출 과정에서 실시간으로 조건을 검사하는 방식을 채택했습니다.

핵심 최적화 전략

• 상향식 가지치기 (Upper Pruning): 숫자를 하나 고를 때마다 현재까지 맞춘 개수가 정답($ans$)을 초과하면 즉시 해당 경로를 포기합니다.
• 하향식 가지치기 (Lower Pruning): 앞으로 남은 숫자를 모두 다 선택하더라도 정답($ans$) 개수를 채울 수 없는 경우 탐색을 중단합니다.
• Pre-processing (Counting Grid): 특정 숫자가 어떤 쿼리에 포함되어 있는지 매번 리스트를 순회하지 않고, boolean[][] countingQ 배열을 통해 $O(1)$로 즉시 확인합니다.

코드

import java.util.*;

class Solution {
    /**
     * @param n 전체 숫자의 범위 (1 ~ n)
     * @param q 시도한 숫자들의 배열
     * @param ans 각 시도에서 맞춘 숫자의 개수
     * @return 가능한 비밀 코드의 조합 개수
     */
    public int solution(int n, int[][] q, int[] ans) {
        // 전처리: 각 숫자가 몇 번째 쿼리에 포함되어 있는지 격자판에 기록
        boolean[][] countingQ = new boolean[q.length][n + 1];
        
        for (int i = 0; i < q.length; i++) {
            for (int j : q[i]) {
                countingQ[i][j] = true;
            }
        }
        
        // 백트래킹 시작
        return bf(0, 0, new int[ans.length], ans, countingQ, n);
    }

    static int bf(int cnt, int cur, int[] tmp, int[] ans, boolean[][] countingQ, int N) {
        // 1. 베이스 조건: 5개의 숫자를 모두 고른 경우
        if (cnt == 5) {
            // 모든 쿼리 조건을 만족하는지 최종 확인
            return Arrays.equals(tmp, ans) ? 1 : 0;
        }
        
        int total = 0;
        // 2. 조합 탐색 (루프 범위 최적화: N - 4 + cnt)
        for (int i = cur + 1; i <= N - 4 + cnt; i++) {
            boolean flag = false;
            
            // [상향식 가지치기] 선택한 숫자가 포함된 쿼리들의 카운트 증가 및 초과 검사
            for (int j = 0; j < countingQ.length; j++) {
                if (countingQ[j][i]) {
                    tmp[j]++;
                    if (tmp[j] > ans[j]) flag = true;
                }
            }
            
            // [하향식 가지치기] 남은 기회(4-cnt)로 정답 개수를 채울 수 있는지 검사
            if (!flag) {
                for (int j = 0; j < countingQ.length; j++) {
                    int need = ans[j] - tmp[j]; 
                    if (need > 4 - cnt) { // 남은 선택 기회보다 더 많이 필요하다면 가망 없음
                        flag = true;
                        break;
                    }
                }
            }
            
            // 3. 조건을 만족하면 다음 숫자 선택 (재귀)
            if (!flag) {
                total += bf(cnt + 1, i, tmp, ans, countingQ, N);
            }
            
            // 4. 백트래킹 복구: 다음 루프를 위해 카운트 감소
            for (int j = 0; j < countingQ.length; j++) {
                if (countingQ[j][i]) {
                    tmp[j]--;
                }
            }
        }
        
        return total;
    }
}