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

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

프로그래머스

최종 코드

import java.util.*;

class Solution {
    private List<String> combinations = new ArrayList<>();
    private List<String> candidateKeys = new ArrayList<>();
    
    public int solution(String[][] relation) {
        int columnSize = relation[0].length;
        //1. 컬럼의 모든 조합 구하기
        for(int i=1; i<=columnSize; i++){
            combi(new boolean[columnSize], columnSize, i, 0);
        }
        
        //2. 각 조합의 중복유무를 검증
        for(String e : combinations){
            if(isCandidateKey(e, relation)){
                candidateKeys.add(e);
            }
        }
        
        return candidateKeys.size();
    }
    
    //3. current에서 문자를 하나씩 제거했을 때 한번이라도 최소성을 위배하는지 확인하고 유일성을 충족하는지 확인 
    private boolean isCandidateKey(String current, String[][] relation){
        StringBuilder sb = new StringBuilder(current);
        int len = sb.length();
        
        for(int i=0; i<len; i++){
            char cur = sb.charAt(i);
            sb.deleteCharAt(i);
            //중복이 없다면 최소성을 위배한 것이다.
            if(!hasDistinct(sb.toString().toCharArray(), relation)){
                return false;
            }
            
            sb.insert(i, cur);
        }
        char[] index = current.toCharArray();
        //최소성 검사 후 전체 컬럼을 놓고 봤을 때 중복이 있는지 확인. 없다면 후보키이다.
        return !hasDistinct(sb.toString().toCharArray(), relation);
    }
    
    //주어진 모든 컬럼의 값을 더해 하나의 컬럼으로 만들고 이 중 중복이 있는지 검사
    private boolean hasDistinct(char[] columnArr, String[][] relation){
        String[] temp = new String[relation.length];
        Arrays.fill(temp, "");
        
        for(int i=0; i<relation.length; i++){
            for(int j=0; j<columnArr.length; j++){
                temp[i]+=relation[i][columnArr[j]-'0'];
            }
        }
        
        int cnt = (int)Arrays.stream(temp).distinct().count();
        return cnt < relation.length;
    }
    
    private void combi(boolean[] visited, int n, int r, int start){
        if(r==0){
            saveCombi(visited);
            return;
        }
        
        for(int i=start; i<n; i++){
            visited[i]=true;
            combi(visited, n, r-1, i+1);
            visited[i]=false;
        }
    }
    
    private void saveCombi(boolean[] visited){
        StringBuilder temp = new StringBuilder();
        for(int i=0; i<visited.length; i++){
            if(visited[i]){
                temp.append(i);
            }
        }
        combinations.add(temp.toString());
    }
}

시나리오

1. 컬럼을 0부터 N으로 설정하고 컬럼의 모든 조합을 구한다.

2. 이후 구한 조합을 순회하며 후보키인지 검증하는데 이 때 최소성과 유일성을 만족한다면 후보키list에 add한다

 

유일성은 한 조합의 로우 중 중복된 것이 없다면 충족한다.

최소성은 컬럼 중 하나라도 제거했을 때 중복된 로우가 없다면 후보키 대상에서 제외되는데 이번 로직에선 한 조합에 컬럼 하나씩 제거해보고 이때 중복된 로우가 발생하는 경우가 한번이라도 있는 경우 후보키 대상에서 제외했다.

알게된 점

StringBuilder insert()

int offset은 StringBuilder객체의 index, 두번째 매개변수는 삽입할 값이다.

 

deleteCharAt과 insert를 함께 사용해서 문제를 풀었는데 dfs에서도 충분히 활용할 수 있어보인다. 다만 insert메서드는 StringBuilder에서도 O(N)의 시간복잡도이므로 n이 크다면 사용을 지양할 필요가 있겠다.

 

최종 코드 이전에는 current가 기존 후보키를 포함하고 있는지 검증했는데 그 때 코드에서는 후보키 stream의 anyMatch를 사용했다.

 

stream().anyMatch(Predicate<? super T> predicate)

         boolean isExist = candidateKeys.stream()
             .anyMatch(key -> {
                 if(current.length()>key.length()){
                     return current.contains(key);
                 } return false;
             });
         if(isExist){return true;}

 

anyMatch는 스트림 요소 중 조건에 해당하는 게 하나라도 있으면 true를 리턴하는 메서드이다.

allMatch는 스트림의 모든 요소가 조건에 충족하면 true 리턴, noneMatch는 조건에 충족하는 요소가 하나라도 있으면 false를 리턴한다.