프로그래머스 - 비밀 코드 해독

문제 링크 ▶︎ 비밀 코드 해독

문제 파악

비밀 코드의 조합이 필요하고 해당 조합이 q와 ans에 적합한지 검사하는 과정이 필요하다고 생각했다.
그래서 오름차순의 조합을 백트래킹으로 구현하면 될 것 같고, 조합된 비밀 코드가 주어진 q와 ans에 적합한 코드인지 검사하는 과정은 q와 ans의 길이가 짧아 완전 탐색으로 해도 충분할 것 같다.

접근 방법

1. 서로 중복이 허용되는 코드이기 때문에 오름차순의 백트래킹을 활용하면 되는데, List에다가 1부터 시작해서 n까지 길이가 5인 코드를 만들어준다.

2. 백트래킹 함수안에서 만약 길이가 5에 도달하게 된다면 그때는 해당 코드를 가지고 적validation이라는 합성 검사를 진행한다.

3. List에 담긴 코드를 검사하기 위해서 q의 길이만큼 돌면서 해당 q의 각 아이템을 모두 List에 포함되어 있는지 체크하고 그 갯수를 세아려서 적합성을 검사한 후 true, false를 리턴한다.

4. 다시 백트래킹 함수로 돌아와 모든 적합성 검사를 통과한 코드라면 answer++ 을 하고 해당 백트래킹 노드를 끊기 위해서 리턴한다.

코드 구현

import java.util.*;
class Solution {
    public int answer;
    public int solution(int n, int[][] q, int[] ans) {
        answer = 0;
        bt(new ArrayList<>(), n, 1, q, ans);
        return answer;
    }
    public void bt(List<Integer> code, int n, int start, int[][] q, int[] ans) {
        if (code.size() == 5) {
            if (validation(code, q, ans)) {
                answer++;
            }
            return;
        }
        for (int i=start; i<=n; i++) {
            code.add(i);
            bt(code, n, i+1, q, ans);
            code.remove(code.size()-1);
        }
    }
    public boolean validation(List<Integer> code, int[][] q, int[] ans) {
        for (int i=0; i<q.length; i++) {
            int cnt = 0;
            for (int item : q[i]) {
                if (code.contains(item)) {
                    cnt++;
                }
            }
            if (cnt != ans[i]) {
                return false;
            }
        }
        return true;
    }
}

개선 사항

어차피 중복되지 않는 비밀 코드였기 때문에 만약 List가 아니라 Set으로 해도 로직에 문제가 없었을 것 같고, 오히려 시간복잡도 측면에서 유리했을 것 같다.