[프로그래머스] 후보키 (Java)

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

코딩테스트 연습 - 후보키

import java.util.*;

class Solution {
    static int row, col;
    static Set<String> ans=new HashSet<>();
    static String[][] r;
    public int solution(String[][] relation) {
        row=relation.length;
        col=relation[0].length;
        r=relation;
        for (int i=1; i<=col; i++){
            comb(i, 0, 0, new boolean[col]);
        }
        return ans.size();
    }
    
    public void comb(int target, int start, int count, boolean[] check){
        if (count==target){
            //minimality
            String s=checkMinimal(check);
            if (s.length()>0)
                make(check, s);
            return;
        }
        for (int i=start; i<col; i++){
            check[i]=true;
            comb(target, i+1, count+1, check);
            check[i]=false;
        }
    }
    
    public String checkMinimal(boolean[] check){
        StringBuilder candidate=new StringBuilder("");
        for (int i=0; i<col; i++){
            if (check[i]){
                candidate.append(i);
            } 
        }
        String s=new String(candidate);
        boolean isMinimal=true;
        for (int i=1; i<s.length(); i++){
            if (!isDuplicate(0,0,i,s.toCharArray(), new char[i])){
                isMinimal=false;
                break;
            }
        }
        
        if (isMinimal)
            return s;
        else
            return "";
    }
    
    public boolean isDuplicate(int start, int count, int total, char[] candidate, char[] cArr){
        if (count==total){
            String s=new String(cArr);
            if (ans.contains(s)) return false;
            return true;
        }
        for (int i=start; i<candidate.length; i++){
            cArr[count]=candidate[i];
            if (!isDuplicate(i+1, count+1, total, candidate, cArr))
                return false;
        }
        return true;
    }
    
    public void make(boolean[] check, String s){
        Set<String> set=new HashSet<>();
        boolean isUnique=true;
        for (int i=0; i<row; i++){
            StringBuilder key=new StringBuilder("");
            for (int j=0; j<col; j++){
                if (check[j]){
                    key.append(r[i][j]);
                }
            }
            if (!set.contains(key.toString())){ //유일성
                set.add(key.toString());
            }
            else{
                isUnique=false;
                break;
            }
        }
        if (!isUnique) return;
        ans.add(s);
    }
}

너무 복잡하게 풀었다..

 

1. 일단 key를 1개 column~n개 column 만큼 조합해서 뽑는다.

2. 각 조합을 할 때, 최소성을 판단한다 

 checkMinimal 함수: 0번째, 1번째, 3번째 column을 고른다면 "013" 으로 문자열을 만들어주고, 

그 문자열을 1개~(문자열의 길이-1)개만큼 조합을 돌려, 후보키를 가진 ans 에서 그와 동일한 것이 있을 경우 false를 리턴한다.

3. 최소성을 만족한 키에 대해, 유일성을 만족하는지 체크한다.

 make 함수: Set을 하나 선언하고, 각 골라진 column에 대해 stringbuilder 을 이용해 각 row마다 선택된 column에 있는 내용을 붙여간다. 만약 해당 set에 같은 내용(즉 같은 키)이 있을 경우(contains), 유일성을 만족하지 못하므로 ans에 넣어주지 않는다. 각 row가 모두 각각 다른 키를 가질 경우, ans에 넣어준다.

 

그런데 문제를 풀 때 최소성을 판단하는 방법이 안떠올라서 결국 선택된 column들을 붙인 문자열에 대해, 조합을 모두 돌려가면서 ans와 비교를 하는 식으로 진행했다.. 이부분이 아쉬웠다.

다른 분들의 코드를 보니, ans에 있는 내용을 하나씩 비교해가면서 만약 ans에 있는 string중 그 string에 있는 것을 모두 포함한다면, 최소성을 만족하지 않는 것으로 구현하였다. (ex: "013"을 넣으려 하고 , ans중 "03" 이 있을 때, "03" 을 "013" 과 비교했을 때, 자신의 모든 문자가 "013" 에 있으면 최소성을 만족 x)

import java.util.*;

class Solution {
    static int row, col;
    static List<String> ans=new ArrayList<>();
    static String[][] r;
    public int solution(String[][] relation) {
        row=relation.length;
        col=relation[0].length;
        r=relation;
        for (int i=1; i<=col; i++){
            comb(i, 0, 0, new boolean[col]);
        }
        return ans.size();
    }
    
    public void comb(int target, int start, int count, boolean[] check){
        if (count==target){
            //minimality
            String s=checkMinimal(check);
            if (s.length()>0)
                make(check, s);
            return;
        }
        for (int i=start; i<col; i++){
            check[i]=true;
            comb(target, i+1, count+1, check);
            check[i]=false;
        }
    }
    
    public String checkMinimal(boolean[] check){
        StringBuilder candidate=new StringBuilder("");
        for (int i=0; i<col; i++){
            if (check[i]){
                candidate.append(i);
            } 
        }
        String s=new String(candidate);
        boolean isMinimal=true;
        for (int i=0; i<ans.size(); i++){
            String tmp=ans.get(i);
            boolean flag=false;
            for (int j=0; j<tmp.length(); j++){
                if (s.indexOf(tmp.charAt(j))==-1){  //없을 경우 
                    flag=true;
                }
            }
            if (!flag){
                isMinimal=false;
                break;
            }
        }
        if (isMinimal)
            return s;
        else
            return "";
    }
    
    
    public void make(boolean[] check, String s){
        Set<String> set=new HashSet<>();
        boolean isUnique=true;
        for (int i=0; i<row; i++){
            StringBuilder key=new StringBuilder("");
            for (int j=0; j<col; j++){
                if (check[j]){
                    key.append(r[i][j]);
                }
            }
            if (!set.contains(key.toString())){ //유일성
                set.add(key.toString());
            }
            else{
                isUnique=false;
                break;
            }
        }
        if (!isUnique) return;
        ans.add(s);
    }
}

위를 반영하여 다시 짠 코드다.

실행속도가 위 코드보다 확실히 빨랐다.

 

ans에 있는 문자열들을 모두 현재 key와 비교해서, ans에 있는 문자열에 속한 문자가 모두 key에 있는 경우, 이는 minimality 를 만족하지 않는 경우임을 체크하는것이 포인트다. (checkMinimal 부분)