후보키

Posted on Edited on In , ,

문제정의

릴레이션이 주어질 때, 후보키가 될 수 있는 경우의 수를 구하는 문제이다. 후보키에 대한 자세한 설명은 문제 원문에 주어졌으니 참고하길 바란다.

문제 링크

문제풀이

전체 코드는 다음과 같다. 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
package level2;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.HashMap;

public class CandidateKey {

    //프로그래머스 문제풀이 level2 후보키
    public static String[][] table;
    public static int answer;
    public static HashMap<String, Integer> map = new HashMap<>();
    public static ArrayList<String> keys = new ArrayList<>();
    public static void main(String[] args) {
        String[][] relation = {
            {"b","2","a","a","b"},
            {"b","2","7","1","b"},
            {"1","0","a","a","8"},
            {"7","5","a","a","9"},
            {"3","0","a","f","9"}
        };
        answer = 0;
        table = new String[relation.length][relation[0].length];
        
        for(int i = 0; i < relation.length; i++)
        {
            for(int j = 0; j < relation[0].length; j++)
                table[i][j] = relation[i][j];
        }
        
        int k = 1;
        String idx = "";
        while(k <= relation[0].length)
            ReturnIndex(0, k++, idx, -1);
        
        System.out.println(answer);
    }
    public static void ReturnIndex(int size, int k, String idx, int start_idx)
    {
        if(size == k)
        {
            for(int i = 0; i < table.length; i++)
            {
                String[] arr = idx.split("");
                StringBuilder buff = new StringBuilder();
                for(String s : arr)
                {
                    buff.append(table[i][Integer.parseInt(s)]);
                    buff.append(" ");
                }
                if(map.getOrDefault(buff.toString(), 0) != 0)
                {
                    map.clear();
                    return;
                }
                map.put(buff.toString(), 1);
            }
            for(String s : keys)
            {
                char[] key = s.toCharArray();
                char[] idx_arr = idx.toCharArray();
                Arrays.sort(key);
                Arrays.sort(idx_arr);
                int k_i = 0;
                for(int i = 0; i < idx_arr.length; i++)
                {
                    if(key[k_i] == idx_arr[i])
                    {
                        k_i++;
                    }
                    if(k_i == key.length)
                        return;
                }
            }
            answer++;
            keys.add(idx);
            map.clear();
        }
        else
        {
            for(int i = start_idx+1; i < table[0].length; i++)
            {
                ReturnIndex(size+1, k, idx+String.valueOf(i), i);
            }
        }
        
    }
    
}
코드가 긴 편인데 과정을 살펴보면 후보키가 될 수 있는 모든 조합을 만들어보고 검사하는 것이다. 원소의 개수가 k개인 부분집합을 검사해주는 함수를 만들어서 k를 1부터 행의 갯수만큼 돌려보면 모든 경우의 수를 다 볼 수 있다. 메인쪽은 간단하기 때문에 함수만 보도록하자.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
public static void ReturnIndex(int size, int k, String idx, int start_idx)
{
    if(size == k)
    {
        for(int i = 0; i < table.length; i++)
        {
            String[] arr = idx.split("");
            StringBuilder buff = new StringBuilder();
            for(String s : arr)
            {
                buff.append(table[i][Integer.parseInt(s)]);
                buff.append(" ");
            }
            if(map.getOrDefault(buff.toString(), 0) != 0)
            {
                map.clear();
                return;
            }
            map.put(buff.toString(), 1);
        }
        for(String s : keys)
        {
            char[] key = s.toCharArray();
            char[] idx_arr = idx.toCharArray();
            int k_i = 0;
            for(int i = 0; i < idx_arr.length; i++)
            {
                if(key[k_i] == idx_arr[i])
                {
                    k_i++;
                }
                if(k_i == key.length)
                    return;
            }
        }
        answer++;
        keys.add(idx);
        map.clear();
    }
    else
    {
        for(int i = start_idx+1; i < table[0].length; i++)
        {
            ReturnIndex(size+1, k, idx+String.valueOf(i), i);
        }
    }
    
}

매개변수에 대해 설명을 하자면 size는 현재 집합에 들어가있는 원소의 개수, k는 만들고자 하는 부분집합의 크기이다. idx는 부분집합에 들어가있는 원소를 나타낸다. 가령 1,2행으로 만들고자 한다면 idx에는 "12"가 들어가있다. start_idx는 이제부터 집어넣을 행을 나타낸다. 중복을 없애기 위해 strat_idx를 넣었다고 보면 된다.

종료조건을 먼저 생각해보자 size가 k가 되면 일단 튜플을 고유하게 분류할 수 있는지 봐야한다. 이를 위해 map을 활용하였다. idx에 있는 행번호를 가져와 map의 키를 생성한다. 이 예제에서 만약 idx가 "12"라면 "b 2", "b 2", "1 0", "7 5","3 0"으로 만들어질 것이다. 키를 만들 때 공백을 넣어주는데 이유가 있다. 수학11점과 과학1점, 과학11점과 수학1점은 다르기 때문이다. 숫자만 합하면 111이지만 다른 정보이기 때문에 다른 키 값으로 간주된다.

키를 만들 때마다 맵에서 똑같은 키 값이 존재하는 지 확인한다. 만약 똑같은 키값이 있다면 1이 반환되므로 이때는 맵을 클리어한 뒤 바로 함수를 종료한다.

맵에서 중복되지 않으면 고유성을 통과했으니 이제 유일성을 확인할 차례이다. 이 부분에서 꽤나 골머리를 앓았는데 contains를 쓰면 틀린다는 사실을 몰랐기 때문이다. "abcd"에서 "ad"는 부분집합이지만 contains로는 이를 판별할 수 없다. 그래서 이를 위한 처리를 해야한다. 두 문자열을 문자배열로 바꾼 뒤, 이미 있는 키들의 부분집합 관계인지 하나하나 확인하는 코드를 짰다. 만약 key가 idx의 부분집합이라면, k_i가 key의 크기가 될 것이고 이 때 바로 함수를 종료한다.

유일성도 통과가 되었다면, 정답을 1증가하고 키값에 idx를 추가한다. 맵도 전부 지워준다.

만약 사이즈를 만족하지 못했다면 원소를 더 넣어봐야 하므로 start_idx+1부터 행의 끝까지 함수를 재호출한다.

최종시간복잡도는 행의 길이를 n이라 했을 때 모든 부분집합을 따져보므로 \(O(n^n)\)이다. 살인적인 시간복잡도지만 테스트케이스 크기가 크지 않다는 것에 주목하자.

테스트