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

비밀 코드 해독

문제

---

문제 설명

어릴 때 했던 숫자야구랑 비슷한데 스트라이크랑 볼의 개념이 아니고 그냥 무조건 오름차순으로 주어졌을 때 일치하는 개수를 알려주면 그것으로 조합되는 개수를 구하는 문제이다.

---

구현

처음에 생각했던 거는 "시스템 응답으로 오는 거만큼 계산해서 잘 조합을 해서 답을 도출을 해봐야 하나?" 라는 생각이였는데 도저히 가닥이 안나왔다.

내가 5개 입력해서 2개 맞으면 5개 중에서 2개 골라서 조합해놓고, 3개 맞으면 5개 중 3개 조합하고 뭐 이렇게 생각이 빠지니깐 계속 그쪽으로만 생각해서 도저히 못풀겠어서 인터넷에서 풀이를 참고했다.

결론은 그냥 백트래킹으로 모든 경우의 수를 구하고 조건에 맞는지 확인하고 맞으면 개수를 늘려주면 되는 생각보다는 간단한 백트래킹 문제였다.

처음에 생각은 하긴 했는데 설마 그렇게 풀까.. 라는 생각으로 접근하지 않았던 게 문제같다.

백트래킹으로 모든 경우의 수를 구하는 시간복잡도는 O(n^5) 일거고 검증과정은 q의 길이만큼 해야하기 때문에 O(q.length) 라고 보면 전체의 시간복잡도는 O(n^5 * q.length) 가 된다.

문제에서 주어진 n의 최대는 30이고 q의 길이는 최대 10이니깐 243,000,000 정도가 나오는데 이정도면 통과하나보다 라고 생각해야겠다.

일단 질문의 개수만큼의 Set을 선언한 뒤에 해당 Set에 정수들을 넣어준다. 이 Set은 나중에 내가 구한 조합이 유효한지 확인할 때 쓸 예정이다.

//입력한 정수들 저장하는 HashSet 선언 및 초기화
Set<Integer>[] set = new Set[q.length];
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를 선언을 해놓고 숫자들을 조합해줄 backTrack 함수를 구현하면 된다.

backTrack 함수에는 조합의 index 를 뜻하는 depth, n개 중에서 어떤 원소를 고를지 정하는 cur, 그리고 기존의 함수에서 넘어오는 세가지 자료들을 넣어주었다.

이 부분은 그냥 백준의 N과 M(2) 문제와 같이 구현해주면 된다.

그 다음으로 검증과정인 isValid 함수에서는 질문으로 들어오는 q와 시스템 응답 배열인 ans를 들고와서 구현한다.

아까 선언해둔 set을 이용해서 내가 입력한 정수들을 기반으로 조합들을 확인하고 내가 만든 조합이 일치하는 개수와 시스템 응답이 일치하지 않으면 false를, 그렇지 않으면 true를 리턴하는 방식으로 구현했다.

---

코드

import java.util.*;

class Solution {
    int[] arr = new int[5];
    boolean[] visited;
    Set<Integer>[] set;
    int answer = 0;
    
    public int solution(int n, int[][] q, int[] ans) {
        //입력한 정수들 저장하는 HashSet 선언 및 초기화
        set = new Set[q.length];
        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];
        backTrack(0, 1, n, q, ans);
        return answer;
    }
    
    public void backTrack(int depth, int cur, int n, int[][] q, int[] ans){
        if(depth == 5){
            if(isValid(q, ans)){
                answer++;
            }
            return;
        }
        //가능한 모든 조합 시도
        for(int i = cur; i <= n; i++){
            if(visited[i])
                continue;
            arr[depth] = i;
            visited[i] = true;
            backTrack(depth + 1, i + 1, n, q, ans);
            visited[i] = false;
        }
    }
    
    public boolean isValid(int[][] q, int[] ans){
        for(int i = 0; i < q.length; i++){
            int sum = 0;
            for(int num : arr){
                if(set[i].contains(num))
                    sum++;
            }
            //시스템의 응답과 카운트 개수가 다르면 false를 리턴
            if(ans[i] != sum)
                return false;
        }
        //같으므로 true 리턴
        return true;
    }
}