[Programmers] 비밀 코드 해독 JAVA

반응형

728x90

[Programmers] 비밀 코드 해독 - LV 2

---

접근

• dfs

---

풀이

2025 프로그래머스 코드챌린지 1차 예선의 2번째 비밀 코드 해독 문제이다. 비밀 코드 자체를 맞춰야 하는 것은 아니고 비밀 코드가 될 수 있는 모든 코드의 개수를 구하는 문제이다. 입력한 비밀 코드는 5개로 이루어져 있고 오름차순 정렬된 상태로 주어진다. 입력한 비밀 코드와 정답인 비밀 코드와 일치하는 코드의 개수가 배열로 같이 주어지기 때문에 두 가지를 보고 가능한 모든 비밀 코드의 개수를 찾아내야 한다. 

 

다른 방법이 딱히 떠오르지 않거나 딱 봐도 매우 복잡해 보인다면 보통 무식하게 풀어질 수 있을지 체크한다. 모든 조합을 구한 뒤 입력한 정수와 비교하여 시스템 응답이 일치하는지 체크해 보는 방법이다. 등장하는 숫자는 최대 30까지로 1부터 30까지 겹치지 않는 5개의 숫자를 뽑을 수 있는 조합의 개수는 142,506개라고 한다. 그렇다면 숫자를 만드는데 드는 최대 연산수가 142,506 그리고 입력한 시도의 최대 횟수는 10으로 대충 최대 1,425,060번의 연산이 수행될 것 같으니 완전 탐색을 통해 모든 조합을 구하고 백트래킹으로 불필요한 반복을 좀 쳐낸다면 충분히 가능해 보이는 숫자이다. 

    private int answer;

    public int solution(int n, int[][] q, int[] ans) {
        answer = 0;
        dfs(1, n, 0, new ArrayList<>(), q, ans);
        return answer;
    }

    private void dfs(int start, int n, int count, List<Integer> current, int[][] q, int[] ans) {
        if (count == 5) {
            checkAns(current, q, ans);
            return;
        }

        for (int i = start; i <= n; i++) {
            current.add(i);
            dfs(i + 1, n, count + 1, current, q, ans);
            current.remove(current.size() - 1);
        }
    }

dfs를 통해 모든 조합을 만들어 주고 만들어지는 조합은 리스트로 관리했다. dfs를 사용했기 때문에 다음 단계로 진행한 뒤 다시 마지막 원소를 제거해 해당 레벨에서 모든 조합을 탐색할 수 있게 해 줬다. 

    private void checkAns(List<Integer> current, int[][] q, int[] ans) {
        Set<Integer> set = new HashSet<>(current);

        for (int i = 0; i < ans.length; i++) {
            int[] code = q[i];
            int count = 0;

            for (int c : code) {
                if (set.contains(c)) {
                    count++;
                }
            }
            
            if (count != ans[i]) {
                return; 
            }
        }  
        answer++;
    }

조합이 완성되었을 때 시스템 응답과 일치하는지 체크하는 메서드이다. Set을 이용해 응답과 일치하는 개수를 구해줬다. 입력한 정수가 Set에 들어있다면 count를 올려 시스템 응답과 일치하는지 체크하고 하나라도 일치하지 않는다면 return으로 불필요한 반복을 없애줬다. 

---

전체 코드

import java.util.*;

class Solution {
    private int answer;

    public int solution(int n, int[][] q, int[] ans) {
        answer = 0;
        dfs(1, n, 0, new ArrayList<>(), q, ans);
        return answer;
    }

    private void dfs(int start, int n, int count, List<Integer> current, int[][] q, int[] ans) {
        if (count == 5) {
            checkAns(current, q, ans);
            return;
        }

        for (int i = start; i <= n; i++) {
            current.add(i);
            dfs(i + 1, n, count + 1, current, q, ans);
            current.remove(current.size() - 1);
        }
    }

    private void checkAns(List<Integer> current, int[][] q, int[] ans) {
        Set<Integer> set = new HashSet<>(current);

        for (int i = 0; i < ans.length; i++) {
            int[] code = q[i];
            int count = 0;

            for (int c : code) {
                if (set.contains(c)) {
                    count++;
                }
            }
            
            if (count != ans[i]) {
                return; 
            }
        }  
        answer++;
    }
}