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

출처

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

프로그래머스

문제

 

문제 자체는 이해하기에 어렵지 않다. 데이터 베이스에서 후보키란, 유일성과 최소성을 만족하는 속성이다. 학생들의 인적사항이 주어졌을때, 후보키의 최대 수를 구하면 되는 문제이다. 

 

즉, 유일하기 때문에 식별이 가능해야하고, 불필요한 속성을 포함하지 않고 최소한의 속성만 포함하도록 해야한다.

 

풀이

후보키를 찾기 위해서 특별한 알고리즘이 존재하지 않는다. 결국 모든 속성의 쌍을 보고, 이것이 유일성과 최소성을 만족하는지 검사하는 방법밖에 없다. 그러므로  이 문제는 완전탐색으로 해결할 수 있다. 다음과 같은 단계를 따라 해결해보겠다.

 

먼저, 존재하는 속성들의 모든 조합을 구해야 한다. 속성이 5개라면 1개부터 5개 까지 조합을 구해, 이것이 유일성을 만족하는지 먼저 검사를 한다.

 

자바에서는 조합을 어떻게 구현하는가? 파이썬이면 Combination 함수 한번만 호출해야 하지만, 자바에서는 DFS로 직접 구현해주어야 한다.

import java.util.*;
class Solution {
    int answer, size;
    
    public int solution(String[][] relation) {
        answer = 0;
        size = relation[0].length;
        // 속성들의 인덱스 조합을 저장할 리스트
        List<List<Integer>> list = new ArrayList<>();
        for (int i = 1; i <= size; i++) {
            // 1개부터 n개까지, 속성의 조합을 구함
            dfs(relation, i, 0, list, new ArrayList<>());
        }
        
        
        return list.size();
    }
    
    public void dfs(String[][] relation, int n, int start, List<List<Integer>> list, List<Integer> now) {
        // now는 현재 만든 조합. n개를 모두 담았다면, 종료 조건이 충족
        if (n == now.size()) {
           // 종료 조건
        }
        
        for (int i = start; i < size; i++) {
            now.add(i);
            dfs(relation, n, i+1, list, now);
            now.remove(now.size() - 1);
        }
    }
}

 

 

먼저 만든 후보키의 조합(속성들의 인덱스만 담아놓는다)을 담을 이중 리스트를 선언한다. dfs에서는 현재까지 선택한 속성의 인덱스를 넣어두기 위해 now라는 리스트를 추가로 매개변수로 받아온다. 

만약 n개까지 선택을 완료하였다면, 먼저 유일성을 검사한다.

// 저장한 속성의 유일성을 판단하기 위한 set
Set<List<String>> set = new HashSet<>();
// now에 들어있는 속성의 인덱스를 바탕으로, set에 속성의 값의 리스트를 넣음
for (int i = 0; i < relation.length; i++) {
    List<String> tmp = new ArrayList<>();
    for (int x: now) {
        tmp.add(relation[i][x]);
    }
    set.add(tmp);
}

 

유일성을 만족하는지 알아보기 위해서, set 자료형에 넣은 다음 원래의 list와 길이가 같은지 비교한다. 유일성 검증이 되었다면, 최소성을 검사한다.

// 넣은 속성의 값 중 중복되는 것이 있는지 확인
if (set.size() == relation.length) {
    boolean flag = true;
    // 만약 중복되는 것이 없다면, 유일성을 충족한다.
    // 최소성을 검사하기 위해, 기존에 list에 저장해두었던 후보키를 확인하여 중복되는 속성의 갯수를 세고
    for (List<Integer> x : list) {
        int cnt = 0;
        for (int y : now) {
            if (x.contains(y)) {
                cnt++;
            }
        }

        // 만약 기존 후보키에 있던 속성이 전부 새로 만든 조합의 속성에 들어있다면
        if (cnt == x.size()) {
            // 새로 만든 후보키 조합은 최소성을 만족하지 못한다.
            flag = false;
        }
    }
    if (flag) {
        list.add(new ArrayList<>(now));
    }
}

 

최소성을 검사하는법은 간단하다. 지금 dfs는 조합하는 속성의 갯수를 1개 -> n개 순서로 늘려가고 있다. 따라서 n개 중 1개를 선택하는 경우 -> n개중 n개를 선택하는 경우 순서로 조합을 만들어내고 있다.

 

이를 이용하여, 최소성을 검사한다.

만약 [0] 또는 [1] 하나로만 후보키가 만들어 졌다면 현재 list에는 [ [0], [1] ] 과 같이 들어있을 것이다. 이후 [0, 2] 조합이 만들어 지고 유일성을 만족한다면, 이 키는 최소성을 만족하는가? 아니다. 왜냐하면 [0, 2]에서 2를 제외하여도 유일성이 깨지지 않기 때문이다.

 

또 다른 예시로, [ [0, 2] ] 의 후보키가 list에 들어 있다고 하자. [0, 1, 2]와 [0, 2, 3], [0, 2, 4] 등은 최소성을 만족하지 못한다. 왜냐면 셋 모두 0과 2를 포함하고 있기 때문에, 하나를 제외해도 유일성이 깨지지 않기 때문이다. 그렇다면 [0, 3]은 최소성을 만족하는가? 0은 [0, 2]에 포함되어 있지만 3은 포함되어 있지 않다.

 

이 원리를 이용하여 최소성 검사를 구현한다면, list에 있는 후보키를 순회하여, 기존 list에 있는 후보키가 "모두" 새로 만든 조합의 후보키에 존재한다면, 새로 만든 속성의 조합은 후보키라고 부를 수 없다. (나머지 속성은 필요가 없기 때문)

 

코드로 보면 이해가 더 잘될 것이다. 

 // 넣은 속성의 값 중 중복되는 것이 있는지 확인
if (set.size() == relation.length) {
    boolean flag = true;
    // 만약 중복되는 것이 없다면, 유일성을 충족한다.
    // 최소성을 검사하기 위해, 기존에 list에 저장해두었던 후보키를 확인하여 중복되는 속성의 갯수를 세고
    for (List<Integer> x : list) {
        int cnt = 0;
        for (int y : now) {
            if (x.contains(y)) {
                cnt++;
            }
        }

        // 만약 기존 후보키에 있던 속성이 전부 새로 만든 조합의 속성에 들어있다면
        // ex) x = [0, 2], y = [0, 1, 2] 라면 cnt는 2. x의 길이와 동일하다면 후보키 X
        // 즉, 후보키인 x의 속성이 "모두" y에 존재한다는 말은 나머지를 제거해도 후보키라는 말이기 때문에 후보키가 아니다.
        if (cnt == x.size()) {
            // 새로 만든 후보키 조합은 최소성을 만족하지 못한다.
            flag = false;
        }
    }
    if (flag) {
        list.add(new ArrayList<>(now));
    }
}

 

코드

import java.util.*;
class Solution {
    int answer, size;
    
    public int solution(String[][] relation) {
        answer = 0;
        size = relation[0].length;
        // 속성들의 인덱스 조합을 저장할 리스트
        List<List<Integer>> list = new ArrayList<>();
        for (int i = 1; i <= size; i++) {
            // 1개부터 n개까지, 속성의 조합을 구함
            dfs(relation, i, 0, list, new ArrayList<>());
        }
        
        
        return list.size();
    }
    
    public void dfs(String[][] relation, int n, int start, List<List<Integer>> list, List<Integer> now) {
        // now는 현재 만든 조합. n개를 모두 담았다면, 종료 조건이 충족
        if (n == now.size()) {
            // 저장한 속성의 유일성을 판단하기 위한 set
            Set<List<String>> set = new HashSet<>();
            // now에 들어있는 속성의 인덱스를 바탕으로, set에 속성의 값의 리스트를 넣음
            for (int i = 0; i < relation.length; i++) {
                List<String> tmp = new ArrayList<>();
                for (int x: now) {
                    tmp.add(relation[i][x]);
                }
                set.add(tmp);
            }
            // 넣은 속성의 값 중 중복되는 것이 있는지 확인
            if (set.size() == relation.length) {
                boolean flag = true;
                // 만약 중복되는 것이 없다면, 유일성을 충족한다.
                // 최소성을 검사하기 위해, 기존에 list에 저장해두었던 후보키를 확인하여 중복되는 속성의 갯수를 세고
                for (List<Integer> x : list) {
                    int cnt = 0;
                    for (int y : now) {
                        if (x.contains(y)) {
                            cnt++;
                        }
                    }

                    // 만약 기존 후보키에 있던 속성이 전부 새로 만든 조합의 속성에 들어있다면
                    if (cnt == x.size()) {
                        // 새로 만든 후보키 조합은 최소성을 만족하지 못한다.
                        flag = false;
                    }
                }
                if (flag) {
                    list.add(new ArrayList<>(now));
                }
            }
            return;
        }
        
        for (int i = start; i < size; i++) {
            now.add(i);
            dfs(relation, n, i+1, list, now);
            now.remove(now.size() - 1);
        }
    }
}