[프로그래머스] 비밀 코드 해독 (Java) — DFS

📌 핵심 요약

• 완전 탐색으로 충분한 규모 — n ≤ 30이므로 전체 조합은 C(30, 5) = 142,506개. 모든 조합을 생성해 검사해도 시간 안에 여유롭게 통과한다.
• 조합 DFS의 start 규칙 — 다음 재귀의 시작점은 항상 "방금 고른 값 + 1"이다. 루프의 시작값(start) 기준으로 넘기면 중복이나 누락이 발생한다.
• 가지치기의 근거 — 일치 개수는 증가만 하므로, 어떤 쿼리의 일치 개수가 ans[i]를 초과하는 순간 그 가지는 탈락이 확정된다. 완성 전에 컷할 수 있다.

 

목차

1 문제 이해

Programmers #388352

비밀 코드 해독

10 ≤ n ≤ 30 · 1 ≤ m ≤ 10

난이도: Lv. 2

1부터 n까지의 서로 다른 정수 5개가 오름차순으로 정렬된 비밀 코드가 있다. m번의 시도마다 5개의 정수를 입력하면 시스템은 그중 몇 개가 비밀 코드에 포함되는지 알려준다. 모든 시도 결과(q, ans)가 주어질 때, 비밀 코드로 가능한 조합의 개수를 구하는 문제다.

풀이 과정

1. 1~n 범위에서 오름차순 5개 조합을 DFS로 생성한다.
2. 조합이 완성되면 각 쿼리 q[i]와의 교집합 개수를 센다.
3. 모든 쿼리에서 일치 개수가 ans[i]와 같으면 카운트한다.

핵심은 규모 판단이다. n이 최대 30이므로 전체 조합 수는 C(30, 5) = 142,506개이고, 쿼리는 최대 10개다. 조합 하나당 검사 비용이 크지 않으므로 모든 조합을 만들어 전부 검사하는 완전 탐색이 성립한다.

2 접근 방법

처음에는 모든 조합을 Set에 넣어두고, 쿼리를 하나씩 처리하며 조건에 어긋나는 조합을 지워나가는 후보 소거(candidate elimination) 방식을 떠올렸다.

이 방식도 정답을 낼 수 있고 시간 안에 통과된다. 다만 이 문제는 쿼리가 처음부터 전부 주어져 있으므로 조합을 저장할 필요가 없다는 점을 확인했다.

구분	Set 후보 소거	DFS 즉석 검사
저장 공간	142,506개 조합 전부 저장	O(1) — 현재 조합 하나
객체 생성	주의 List<Integer> 박싱 비용	거의 없음 (int[] 재사용)
구현 난이도	순회 중 삭제, equals 이슈 존재	단순
통과 여부	통과	통과

조합 하나가 어떤 쿼리에서 탈락하면 나머지 쿼리는 검사하지 않고 넘어가면 되므로, Set 방식에서 기대했던 "쿼리마다 집합이 줄어드는 효과"는 즉석 검사에서도 동일하게 얻을 수 있다.

결국 Set의 저장 비용만 순수한 추가 비용으로 남는다고 판단해 DFS 생성 + 즉석 검사 방식을 선택했다.

3 풀이 — DFS로 조합 생성

start 파라미터에서 두 번 틀렸다

오름차순 조합을 만드는 DFS에서 다음 재귀에 넘기는 시작점을 잘못 잡아 두 번 틀렸다. 원인과 결과를 정리하면 다음과 같다.

다음 재귀의 start	동작	결과
start + 1	고른 숫자 i와 무관하게 진행 → 같은 숫자 재선택, 순열 중복 발생	answer 과대
start + i	depth 0에서만 우연히 일치, 깊어지면 멀쩡한 조합을 건너뜀	answer 과소
i + 1	방금 고른 값 기준으로 다음 자리를 제한	정확

💡

조합 DFS의 start 규칙

다음 재귀의 시작점은 항상 "방금 고른 값"에서 파생되어야 한다. start는 이번 루프의 하한을 정하는 역할로 끝나고, 다음 단계로 전달되는 값은 i + 1이다.

1차 정답 코드

 

Java — DFS 생성 + 완성 후 검사

import java.util.*;

class Solution {
    int[] arr = new int[5];
    int n;
    int[][] q;
    int[] ans;
    int answer;

    public int solution(int n, int[][] q, int[] ans) {
        this.n = n;
        this.q = q;
        this.ans = ans;

        dfs(1, 0);

        return answer;
    }

    // start : 이번 자리에 넣을 수 있는 가장 작은 숫자 (오름차순 보장)
    // depth : 지금까지 고른 숫자 개수
    public void dfs(int start, int depth) {
        if (depth == 5) {
            if (isValid(arr)) {
                answer++;
            }
            return;
        }

        for (int i = start; i <= n; i++) {
            arr[depth] = i;
            dfs(i + 1, depth + 1);  // 다음 자리는 방금 고른 i의 다음부터
        }
    }

    public boolean isValid(int[] arr) {
        for (int i = 0; i < q.length; i++) {
            int count = 0;
            for (int j = 0; j < q[0].length; j++) {
                for (int z = 0; z < arr.length; z++) {
                    if (q[i][j] == arr[z]) {
                        count++;
                    }
                }
            }
            if (count != ans[i]) {
                return false;
            }
        }
        return true;
    }
}

dfs가 오름차순 5개 조합을 정확히 한 번씩 생성하고, isValid가 완성된 조합과 각 쿼리의 교집합 개수를 세어 ans[i]와 비교한다. 하나라도 다르면 즉시 탈락시킨다. 이 코드로 통과했다.

4 가지치기 — 만들다가 컷하기

조기 종료와 가지치기는 다르다

처음에는 isValid 안에 if (count > ans[i]) return false;를 넣는 것이 가지치기라고 생각했다. 하지만 이것은 이미 완성된 조합의 검사를 일찍 끝내는 조기 종료일 뿐, 조합 생성 자체를 줄이지는 못한다. DFS는 여전히 142,506개 조합을 전부 만들고 isValid를 전부 호출한다.

ℹ️

가지치기의 판정 근거

일치 개수는 숫자를 고를수록 증가만 하고 감소하지 않는다. 따라서 조합을 만드는 도중 어떤 쿼리의 일치 개수가 ans[i]를 초과하면 그 가지는 어떻게 완성해도 탈락이 확정이다. 반대로 부족한 것은 앞으로 채워질 수 있으므로 컷하면 안 된다.

진짜 가지치기는 dfs 안에서 일어난다. 예를 들어 ans[0] = 1인 쿼리에서 depth 2에 이미 2개를 골랐다면, 그 아래의 수천 개 조합을 만들 필요 없이 그 자리에서 가지 전체를 버릴 수 있다. "완성 후 검사"에서 "만들다가 컷"으로 바꾸는 것이다.

가지치기 적용 코드

 

Java — matchCount 누적 + 중간 가지치기

import java.util.*;

class Solution {
    int[] arr = new int[5];
    int n;
    int[][] q;
    int[] ans;
    int answer;
    int[] matchCount;  // matchCount[i] = 현재까지 고른 숫자 중 q[i]와 일치하는 개수

    public int solution(int n, int[][] q, int[] ans) {
        this.n = n;
        this.q = q;
        this.ans = ans;
        this.matchCount = new int[q.length];

        dfs(1, 0);

        return answer;
    }

    public void dfs(int start, int depth) {
        if (depth == 5) {
            // 이 시점에 matchCount는 완성된 조합의 일치 개수 그 자체
            if (isValid()) {
                answer++;
            }
            return;
        }

        for (int i = start; i <= n; i++) {
            arr[depth] = i;

            // 1. i가 포함된 쿼리들의 일치 개수를 올린다
            boolean over = false;
            for (int j = 0; j < q.length; j++) {
                if (contains(q[j], i)) {
                    matchCount[j]++;
                    if (matchCount[j] > ans[j]) over = true;
                }
            }

            // 2. 초과한 쿼리가 없을 때만 다음 깊이로 진입 (가지치기)
            if (!over) {
                dfs(i + 1, depth + 1);
            }

            // 3. 원상복구 — 올렸던 것을 그대로 내린다
            for (int j = 0; j < q.length; j++) {
                if (contains(q[j], i)) {
                    matchCount[j]--;
                }
            }
        }
    }

    // 완성된 조합이 모든 쿼리를 만족하는지 — 비교 한 줄이면 끝
    public boolean isValid() {
        for (int i = 0; i < q.length; i++) {
            if (matchCount[i] != ans[i]) {
                return false;
            }
        }
        return true;
    }

    public boolean contains(int[] query, int num) {
        for (int x : query) {
            if (x == num) return true;
        }
        return false;
    }
}

숫자를 고르는 순간마다 matchCount에 일치 개수를 누적하므로, depth 5에 도달했을 때는 이미 답이 나와 있다. 1차 코드의 3중 루프 isValid가 matchCount[i] == ans[i] 비교로 대체되었다.

⚠️

원상복구는 무조건 실행되어야 한다

초과(over)가 발생했더라도 matchCount는 이미 올려놓은 상태다. 재귀 진입만 막고 복구 루프는 반드시 통과해야 한다. continue로 건너뛰면 올림/내림의 짝이 어긋나 형제 가지들이 오염된다. 백트래킹에서 가장 실수하기 쉬운 지점이다.

가지치기 효과는 예제 2(ans = [2, 1, 3, 0, 1])에서 잘 드러난다. 네 번째 쿼리의 ans[3] = 0이므로 q[3] = [6, 7, 11, 13, 15]의 숫자를 하나라도 고르는 순간 그 가지가 통째로 잘린다.

5 정리

이번 문제에서 정리한 내용은 세 가지다.

첫째, 규모 계산이 접근을 결정한다. C(30, 5) = 142,506이라는 숫자를 먼저 확인했기 때문에 완전 탐색을 확신할 수 있었고, Set 저장 방식과 즉석 검사 방식의 비용 차이도 판단할 수 있었다.

둘째, 조합 DFS의 다음 시작점은 "방금 고른 값" 기준이다. start + 1(중복 허용)과 start + i(조합 누락)를 거쳐 i + 1에 도달했다. start는 루프의 하한을 정하는 역할로 끝난다는 점을 명확히 했다.

셋째, 조기 종료와 가지치기를 구분해야 한다. 완성된 조합의 검사를 일찍 끝내는 것과 조합 생성 자체를 줄이는 것은 다르다. 후자가 성립하려면 "되돌릴 수 없는 탈락 조건"(여기서는 일치 개수 초과)이 필요하고, 상태를 누적했다면 반드시 원상복구까지 짝을 맞춰야 한다.

잘못된 내용이 있다면 지적부탁드립니다. 방문해주셔서 감사합니다.