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

➡️문제 링크

https://school.programmers.co.kr/learn/courses/30/lessons/388352

 

 

아이디어

문제를 읽으면서 특정 유형의 문제인가 살펴봤는데

아무리 봐도 근거를 찾을 수 없어서 조합+완탐의 뚝심 있는 문제라고 생각해서 풀었다.

 

 

[문제 풀이]

1.조합+완탐 - 오답

조합을 떠올리고 처음에 내가 생각한 아이디어는

각 시스템 단계별로 조합을 구하고, 그다음 단계 조합을 구하는 거였다.

처음에는 와 감잡았네~ 싶었는데,

구현하다보니 하나둘씩 허점들이 보였고(각 단계에서 구한 숫자들을 어떻게 저장할 것인지 등)

돌려보니 테스트케이스부터 모두 실패!

import java.util.*;

/*
아이디어: 완탐? - 조합
*/
class Solution {
    int n;
    int [][] q;
    int [] ans;
    Set<String> hset = new HashSet<>();
    List<Integer> list = new ArrayList<>();
    public int solution(int n, int[][] q, int[] ans) {
        this.n = n;
        this.q = q;
        this.ans = ans;
        
        int answer = 0;
        comb(0, 0, 0, new int[ans[0]], new boolean[n+1], new HashSet<>());
        
        return hset.size();
    }
    
    void comb(int idx, int cnt, int start, int [] combination, boolean [] visited, Set<Integer> set){
        if(cnt == ans[idx-1]){
            // 현재 단계에서 조합 만들어짐
            for(int s : set){
                if(!list.contains(s)) list.add(s);
            }
            
            comb(idx+1, 0, 0, new int[ans[idx]], visited, set);
        }
        
        if( idx == 5){
            // 5 번까지 순회
            if(list.size() != 5) return;
            String str = "";
            for(int num : list){
                str+= num+"";
            }
            hset.add(str);
        }
        
        
        
        for(int i = 0; i < 5; i++){
            if(visited[q[idx][i]]) continue;
            
            combination[cnt] = q[idx][i];
            visited[q[idx][i]] = true;
            set.add(q[idx][i]);
            
            comb(idx, cnt+1, start+1, combination, visited, set);
            visited[q[idx][i]] = false;
            set.remove(q[idx][i]);
            
        }
    }
    
}

 

 

2. 조합+완탐 - 성공

둘 다 조합+완탐인데, 왜 이건 성공한 거야?라는 의문이 들 수 있을 것이다.

바뀐 풀이의 핵심은 바로, 조합을 어떻게 하는가?였다.

나는 기존에는 각 시스템 단계별로 조합을 만들었다.

예를 들어 문제에 나온 것처럼ans = {2, 3, 4, 3, 3} 일 때,

5C2*5C3*5C4*5C3*5C3 이런 식으로 구했다.

 

하지만, 이번에는 문제에서 요구하는 것처럼

1. 5개의 비밀코드를 먼저 구하고

2. 1에서 구한 비밀코드로 2차원 배열 q를 i번째 단계에서 해독한 결과가 ans[i]와 같은지를 보는 것이다.

이렇게 보니 별 거 아닌 것 같죠?

import java.util.*;

/*
아이디어: 완탐? - 조합
-> 1. 5개 조합 만들기

*/
class Solution {
    int n;
    int [][] q;
    int [] ans;
    int answer = 0;
    public int solution(int n, int[][] q, int[] ans) {
        this.n = n;
        this.q = q;
        this.ans = ans;
    
        combine(1, 0, new ArrayList<>());
        
        return answer;
    }
    
    void combine(int start, int cnt, List<Integer> combination){
        if(cnt == 5){
            // 5개 비밀 코드 완성
            checkPath(combination);
            return;
        }
        
        // 각 path별로 조합 만들기
        for(int i = start; i <= n; i++){
            combination.add(i);
            combine(i+1, cnt+1, combination);
            combination.remove(combination.size()-1);
        }
    }
    
    void checkPath(List<Integer> path){
        Set<Integer> set = new HashSet<>(path);
        
        for(int i = 0; i < ans.length; i++){
            // q안에서 검증하기
            int count = 0;
            
            for(int num : q[i]){
                if(set.contains(num)) count++;
            }
            
            // 현재 검출된 숫자와 ans의 검출값 일치 여부 확인
            if(ans[i] != count) return;
        }
        
        answer++;
    }
}