[프로그래머스,Java] Level2: 후보키

 

문제분석

 

문제목표:  데이터를 탐색해서 후보키의 갯수를구하자.

 

특징: 후보키를 구하기위해서   유일성과 최소성이 만족되어야한다.

 

 

데이터베이스의 기초지식이 갖추어져있다면 익숙하겠지만, 모르면 좀 난감하게 와닿을수있다.

 

유일성:  유일하게 식별이 가능한상태 , 즉 이 튜플로 모든데이터를 구별이 가능해야한다.

더 쉽게말하면 중복이 단 하나도없는 컬럼이여만한다.

 

최소성:  예시로 설명하자면, A={1,2}  B={1,2,3} 이면 최소성이 깨진다.

그 이유는, A가 이미 {1,2}로 유일하게 식별이가능한데,  B={1,2,@}는 볼필요도없이 유일하게 식별이가능하다.

B와같은 쓸데없는 후보키를 제거하는것이 최소성이라고한다.

즉,  어떤 컬럼의조합이 다른 컬럼에 포함되면 안된다.

 

 

문제를 읽어보면 우리가 필요한게 컬럼들의 모든 조합이 필요하다.

 

즉 완전탐색이다.  

 

백트래킹을 위한 준비물이다.

visited= 방문체크용

len = 컬럼의 갯수

cnt = 튜플의 갯수 (데이터 갯수)

 

list= HashSet인데, 백트래킹을한 데이터에서 중복을 걸러줘서 리스트에 담을 예정입니다.

 

list2= 답안 (후보키 갯수)입니다. 이 리스트에 저장된 컬럼의조합은 모두 후보키입니다.

 

메인함수 및 백트래킹이다.

 

조합이 1~n개를 뽑기원하기때문에 반복해서 조합을해야한다.

조합의 탈출조건은 r==0일때  방문체크가된 조합을 리스트에 집어넣는다.

 

조합을 마쳤다면, 유일성과 최소성을 따져야한다.

 

먼저 유일성을 따져보자.

유일성을 따지려면,  조합된 컬럼의 데이터 중복을따져봐야한다.

 

따라서 중복을 알아서 걸러주는 set을 새로 추가했다.

만약, set에다 모든 데이터를 넣었는데 set의 데이터갯수가, 기존데이터갯수와 일치하지않으면 중복이 존재하는것이다.

 

 

유일함을 판단했으면 최소성을 구해야한다.

 

최소성은 후보키에 존재하는 list2의 원소를 포함하면 최소성에 맞지않으므로 빼줘야한다.

 

P.s: 보통 Level2는 그냥 백트래킹(완전탐색)만 나와도 충분한난이도인데,  유일성, 최소성검사까지해야한다.

Level3는 줘야하지않나... 

문제풀이

import java.util.*;
class Solution {
 
boolean[] visited; 
int len;
int cnt;
Set<String> list = new HashSet<>();
List<String> list2= new ArrayList<>();
    public int solution(String[][] relation) {
        int answer = 0;
        
        len=relation[0].length;
        cnt=relation.length;
        visited=new boolean[len];
       
        
        for(int i=1;i<=len;i++){
            comb(0,i,relation);           
            unique(relation);
            list.clear();   
        }     
        return list2.size();
    }
 
    public void comb (int start,int r,String[][] relation){     
        if(r==0){
            String temp="";
            for(int i=0;i<len;i++){
                if(visited[i]){
                    temp+=i;
                }
            }
            list.add(temp);
        }      
        for(int i=start;i<len;i++){
            if(!visited[i]){
                visited[i]=true;
                comb(start+1,r-1,relation);
                visited[i]=false;
            }
        }
    }
    
    public void unique(String[][] relation){
        //유일성 판단하기
        for(String data:list){
            String[] temp= data.split("");
            int[] arr=new int[temp.length];
            for(int i=0;i<temp.length;i++){
                int c =Integer.parseInt(temp[i]);
                arr[i]=c;
             }
            //유일성 판단하기위한 set
            Set<String> set = new HashSet<>();
            for(int i=0;i<cnt;i++){
                String cdd="";
              for(String data2:temp){
                int c =Integer.parseInt(data2);
                cdd+=relation[i][c];
              }
                set.add(cdd);
            }
            //만약 유일하다면 최소성 검사
            if(set.size()==cnt){
                boolean flag=false;
                for(String data3:list2){
                    int cnt=0;
                    String[] temp3= data3.split("");         
                    for(String data4:temp3){
                        if(data.contains(data4)){
                            cnt++;
                        }
                    }
                    if(cnt==data3.length()){
                        flag=true;
                    }
                }
                if(!flag){
                   list2.add(data);                             
                }
            }
        }
    }
}