비밀 코드 해독 (Java)

📌 문제 설명

• 1부터 N까지의 숫자 중에서 5개의 숫자를 뽑아 암호를 만든다.
• 주어진 질문(q)은 각각 5개의 숫자로 이루어진 배열이다.
• 각 질문에 대해 정답 배열(ans)의 값은 해당 질문과 암호의 교집합 요소 개수이다.
• 이 조건에 맞는 암호의 개수를 반환하는 문제이다.

문제 링크 🔗

---

🔍 접근 방식

1. 완전 탐색(Brute Force)을 사용하여 가능한 모든 조합을 생성한다.
2. 각 조합에 대해 주어진 질문과 비교하여 맞는지 확인한다.
3. 조건에 맞으면 answer 값을 증가시킨다.

---

💡 구현 방법

1. 조합 생성 (makeArr)

• 1부터 N까지의 숫자 중 5개를 선택하여 배열에 저장한다.
• 백트래킹을 사용하여 중복 없이 숫자를 선택한다.

2. 조건 검증 (compareAns)

• 각 질문과 현재 조합의 교집합 개수를 확인한다.
• 교집합 개수가 ans 배열의 값과 일치하면 다음 질문으로 넘어간다.
• 모든 질문이 일치하면 answer++을 증가시킨다.

3. Set을 사용한 최적화

• 각 질문을 HashSet으로 저장하여 교집합 검사 시 O(1)로 처리한다.

---

🧩 코드 구현

import java.util.*;

class Solution {
    
    int[] arr = new int[5];         // 현재 선택된 5개의 숫자
    boolean[] visited;              // 숫자 사용 여부 확인
    int answer;                     // 최종 정답 개수
    Set<Integer>[] set;             // 각 질문의 숫자를 저장한 HashSet 배열
    
    public int solution(int n, int[][] q, int[] ans) {
        set = new Set[q.length];
        
        // 각 질문의 숫자를 HashSet에 저장 (검색 속도 O(1))
        for (int i = 0; i < q.length; i++) {
            set[i] = new HashSet<>();
            for (int j = 0; j < 5; j++) {
                set[i].add(q[i][j]);
            }
        }
        
        visited = new boolean[n + 1];
        makeArr(0, 1, n, q, ans); // 조합 생성 및 검증 시작
        return answer;
    }
    
    // ✅ 조합 생성 메서드 (Backtracking)
    private void makeArr(int cnt, int cur, int n, int[][] q, int[] ans) {
        // 5개를 모두 선택한 경우
        if (cnt == 5) {
            if (compareAns(q, ans)) answer++;  // 조건에 맞으면 정답 증가
            return;
        }
        
        // cur부터 시작하여 중복 없이 숫자 선택
        for (int i = cur; i <= n; i++) {
            if (visited[i]) continue; // 이미 사용한 숫자는 건너뜀
            arr[cnt] = i;             // 현재 숫자 선택
            visited[i] = true;
            makeArr(cnt + 1, i + 1, n, q, ans); // 재귀 호출로 다음 숫자 선택
            visited[i] = false;        // 백트래킹 (선택 해제)
        }
    }
    
    // ✅ 질문과 현재 조합 비교 메서드
    private boolean compareAns(int[][] q, int[] ans) {
        for (int i = 0; i < q.length; i++) {
            int sum = 0;
            // 현재 조합(arr) 중 질문(set[i])에 포함된 숫자 개수 계산
            for (int num : arr) {
                if (set[i].contains(num)) sum++;
            }
            // 교집합 개수가 주어진 정답과 일치하지 않으면 실패
            if (ans[i] != sum) return false; 
        }
        return true; // 모든 질문의 조건을 만족하면 true 반환
    }
}

---

✅ 알고리즘 설명

1. 완전 탐색 (백트래킹)
   • makeArr() 메서드에서 모든 조합을 생성하며,
   • 매 조합마다 compareAns()로 질문과 비교한다.
2. Set을 통한 빠른 검색
   • 각 질문을 HashSet에 저장하여 O(1)로 교집합 검사를 수행한다.
3. 시간복잡도:
   • 조합의 개수: $ \binom{n}{5} = \frac{n \times (n-1) \times (n-2) \times (n-3) \times (n-4)}{5!}$
   • 각 조합마다 질문과 비교하는 데 걸리는 시간은 O(q)
   • 전체 시간복잡도: O(\binom{n}{5} \times q)

---

💎 성능 최적화

• 기존 방식도 충분히 빠르지만, Set을 사용하여 교집합 검사 속도를 O(1)로 최적화했다.
• 또한, 백트래킹으로 불필요한 탐색을 최소화했다.

---

🧪 테스트 케이스

1. 기본 테스트

int n = 5;
int[][] q = {{1, 2, 3, 4, 5}};
int[] ans = {5};

결과: 1

---

2. 여러 질문

int n = 5;
int[][] q = {
    {1, 2, 3, 4, 5},
    {1, 2, 3, 4, 6}
};
int[] ans = {5, 4};

결과: 1

---

3. 최대 입력 테스트 (성능 확인)

• n = 50, 질문 개수 = 10
• Set 사용 덕분에 효율적으로 탐색 가능

---

💡 문제 해결 과정 요약

1. 완전 탐색(백트래킹)으로 가능한 모든 조합을 생성
2. Set을 사용하여 교집합 검사를 O(1)로 최적화
3. 시간복잡도: O(\binom{n}{5} * q)로, Set 덕분에 효율적으로 작동

---

🚀 최종 결론

• 이 문제는 완전 탐색을 사용하여 해결하는 것이 가장 직관적이다.
• Set을 사용하여 교집합 검사 속도를 O(1)로 최적화함으로써 성능을 개선했다.
• 백트래킹을 통해 중복을 방지하고 효율적으로 탐색한다.