[JAVA] 프로그래머스 LEVEL2 후보키

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

프로그래머스

코딩테스트 연습 > 2019 KAKAO BLIND RECRUITMENT > 후보키

 

난이도: LEVEL2

알고리즘 유형: 구현 + 완전탐색 

틀린 코드

import java.util.*;
class Solution {
    static int n,m; // 컬럼의 개수 / row 개수  
    static boolean [] local;  // 현재 상태 금지 컬럼 
    static int answer = 0;
    static String [][] r;
    static ArrayList<String> keys = new ArrayList<>();
    // 다음 개수에서 후보 키로 사용 못 하는 컬럼들 
    static HashSet<Integer> nextGlobal = new HashSet<>();
    public int solution(String[][] relation) {
        r = relation;
        n = relation[0].length; // 컬럼의 개수 
        m = relation.length; // row 개수 
        local = new boolean [n];
        // 후보키 만들기 i = 후보키 컬럼 개수 
        for(int i = 1; i <= n; i++){
            choose(0, i, 0);
        }
        return answer;
    }
    // cnt: 순서가 다른 케이스 중복 방지용 
    public static void choose(int depth, int end, int cnt){
        if(depth == end){
            candidateKey();
            return;
        }
        for(int i = cnt; i < n; i++){
            if(local[i]) continue;
            local[i] = true;
            choose(depth + 1, end, i + 1);
            local[i] = false;
        }
    }
    public static void candidateKey(){
        HashSet<String> set = new HashSet<>();
        ArrayList<Integer> list = new ArrayList<>();
        for(int i = 0; i < n; i++){
            if(local[i]) list.add(i);
        }
        StringBuilder SB = new StringBuilder();
        for(int next : list){
            SB.append(next);
        }
        String key = SB.toString();
        for(String next : keys){
            if(key.contains(next)) return;
        }
        
        for(int i = 0; i < m; i++){
            StringBuilder sb = new StringBuilder();
            for(int j = 0; j < list.size(); j++){
                sb.append(r[i][list.get(j)]);
            }   
            String row = sb.toString();
            set.add(row);
        }
        if(set.size() != m) return;
        
        keys.add(key);
        answer++;
    }
}

 

현재 틀린 코드를 보면 최소성 테스트를 contains를 통해서 하고 있다.

이렇게 풀면 테스트케이스 18,19,20,22,25 5개가 틀린다.

 

왜 contains는 틀릴까?

 

해당 완탐은 

컬럼의 index 숫자 순서로 동작한다.

 

ex) 컬럼이 3개

0

1

2

01

02

12

012

 

이렇게 컬럼의 index를 통해서 String으로 만들고 

최소성 검사를 contains를 하게 되면 
밑에 케이스에서 틀린다.

 

0, 3 -> 후보키 

0, 1, 2, 3 -> 후보키 후보 

 

contains를 사용하면 "03"은 "0123"에 포함되지 않기 때문에 최소성 검사를 통과하게 된다.

그래서 contains가 아닌 모든 컬럼을 포함하는지에 대한 최소성 검사를 해야 한다. 

 

최소성 검사 변경

static ArrayList<ArrayList<Integer>> keys = new ArrayList<>();

ArrayList<Integer> list = new ArrayList<>(); // 리스트에는 이번에 사용하는 컬럼 index가 들어간다.
for(int i = 0; i < n; i++){
    if(local[i]) list.add(i);
}

// 최소성 테스트 
for(ArrayList<Integer> key : keys){
    int cnt = 0;
    for(int next : key){
        if(list.contains(next)) cnt++;
    }
    if(cnt == key.size()) return;
}

 

정답 코드

import java.util.*;
class Solution {
    static int n,m; // 컬럼의 개수 / row 개수  
    static boolean [] local;  // 현재 상태 금지 컬럼 
    static int answer = 0;
    static String [][] r;
    static ArrayList<ArrayList<Integer>> keys = new ArrayList<>();
    // 다음 개수에서 후보 키로 사용 못 하는 컬럼들 
    static HashSet<Integer> nextGlobal = new HashSet<>();
    public int solution(String[][] relation) {
        r = relation;
        n = relation[0].length; // 컬럼의 개수 
        m = relation.length; // row 개수 
        local = new boolean [n];
        // 후보키 만들기 i = 후보키 컬럼 개수 
        for(int i = 1; i <= n; i++){
            choose(0, i, 0);
        }
        return answer;
    }
    // cnt: 순서가 다른 케이스 중복 방지용 
    public static void choose(int depth, int end, int cnt){
        if(depth == end){
            candidateKey();
            return;
        }
        for(int i = cnt; i < n; i++){
            if(local[i]) continue;
            local[i] = true;
            choose(depth + 1, end, i + 1);
            local[i] = false;
        }
    }
    public static void candidateKey(){
        ArrayList<Integer> list = new ArrayList<>();
        for(int i = 0; i < n; i++){
            if(local[i]) list.add(i);
        }
        // 최소성 테스트 
        for(ArrayList<Integer> key : keys){
            int cnt = 0;
            for(int next : key){
                if(list.contains(next)) cnt++;
            }
            if(cnt == key.size()) return;
        }
        // 유일성 테스트 
        HashSet<String> set = new HashSet<>();
        for(int i = 0; i < m; i++){
            StringBuilder sb = new StringBuilder();
            for(int j = 0; j < list.size(); j++){
                sb.append(r[i][list.get(j)]);
            }   
            String row = sb.toString();
            if(set.contains(row)) return;
            set.add(row);
        }
        keys.add(list);
        answer++;
    }
}