프로그래머스: 후보키

문제

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

코드

코드 출처 https://leveloper.tistory.com/106

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
public int solution(String[][] relation) {

    int columnCount = relation[0].length;
    int rowCount = relation.length;

    List<Integer> list = new ArrayList<Integer>();
    for (int i = 1; i < (1 << columnCount); i++) {
        if (!isUniqueness(relation, i, columnCount, rowCount)) {
            continue;
        }

        if (!isMinimality(i, list)) {
            continue;
        }

        list.add(i);
    }

    return list.size();
}

private boolean isUniqueness(String[][] relation, int set, int columnCount, int rowCount) {
    ArrayList<Integer> columnIndexList = getColumnIndex(set, columnCount);

    HashSet<String> hashSet = new HashSet<>();
    for (int row = 0; row < rowCount; row++) {
        StringBuilder sb = new StringBuilder();

        for (int column : columnIndexList) {
            sb.append(relation[row][column]);
        }

        hashSet.add(sb.toString());
    }

    return hashSet.size() == rowCount;
}

private ArrayList<Integer> getColumnIndex(int set, int colSize) {
    ArrayList<Integer> result = new ArrayList<>();
    for (int i = 0; i < colSize; i++) {
        if (((set >> i) & 1) == 1) {
            result.add(i);
        }
    }

    return result;
}

private boolean isMinimality(int set, List<Integer> list) {
    boolean isMinimality = true;

    for (int i : list) {
        if ((set & i) == i) {
            isMinimality = false;
            break;
        }
    }

    return isMinimality;
}

코드 출처 https://leveloper.tistory.com/106

흐름

예제

예제

예제의 경우의 수

10진수 2진수 부분 집합
1 1 학번
2 10 이름
3 11 학번 이름
4 100 전공
5 101 학번 전공
6 110 전공 이름
7 111 학번 이름 전공
8 1000 학년
9 1001 학번 학년
10 1010 이름 학년
11 1011 학번 이름 학년
12 1100 전공 학년
13 1101 학번 전공 학년
14 1110 이름 전공 학년
15 1111 학번 이름 전공 학년

부분 집합에 매핑되는 2진수

학년 전공 이름 학번
1
1 0
1 1
1 0 0
1 0 1
1 1 0
1 1 1
1 0 0 0
1 0 0 1
1 0 1 0
1 0 1 1
1 1 0 0
1 1 0 1
1 1 1 0
1 1 1 1 


1
2
3
for (int i = 1; i < (1 << columnCount); i++) {
    ...
}
  1. 모든 경우의 수 만큼 반복하기 위해 테이블의 컬럼 수 만큼 1을 왼쪽 시프트 한다.
  2. column이 4 이면 1부터해서 1, 10, 100, 1000, 10000이 되고 10진수로 16이 된다.
  3. 후보키의 조건인 유일성와 최소성을 만족하는 지 확인한다.
  4. 유일성과 최소성을 모두 만족한다면 해당하는 값을 List에 추가한다.
  5. 모든 반복이 끝나면 List의 크기를 return 한다.
  6. 끝

유일성 확인

1
2
3
4
5
6
7
8
9
10
private ArrayList<Integer> getColumnIndex(int set, int colSize) {
    ArrayList<Integer> result = new ArrayList<>();
    for (int i = 0; i < colSize; i++) {
        if (((set >> i) & 1) == 1) {
            result.add(i);
        }
    }

    return result;
}
  1. 10진수를 2진수로 치환하기 위해 오른쪽 시프트 연산자와 And 비트 연산자를 이용한다.
  2. 처음은 1부터 이므로 1을 오른쪽으로 0만큼 시프트하면 그대로 1이고 1과 1을 And 하면 값은 1과 같으므로 리스트에 담는다.
  3. 1을 0 이상 시프트 한다면 0이 되므로 list에는 더 이상 추가 될 수 없다.
  4. set에 2가 들어온 경우엔 2는 위 표에 적힌 것 처럼 2진수로 10이므로 10을 오른쪽으로 0번 시프트하면 10 이므로 1과 and 연산을 하면 0이 된다.
  5. 10을 오른쪽으로 1번 시프트하면 1이 되고 and 연산하면 1이 맞으므로 list에 1을 추가하고 그 이상 시프트 연산해봤자 0이 된다.
  6. set에 3이 들어온 경우엔 3은 위 표에 적힌 것 처럼 2진수로 11이므로 11을 오른쪽으로 0번 시프트하면 11이므로 1과 and 연산하면 1이 맞으므로 list에 0을 추가한다.
  7. 11을 오른쪽으로 1번 시프트하면 1이므로 1과 and 연산하면 1이 맞으므로 list에 1을 추가한다.
  8. 이 처럼 쭉 모든 수를 반복해서 colmn의 index를 구한다.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
private boolean isUniqueness(String[][] relation, int set, int columnCount, int rowCount) {
    ArrayList<Integer> columnIndexList = getColumnIndex(set, columnCount);

    HashSet<String> hashSet = new HashSet<>();
    for (int row = 0; row < rowCount; row++) {
        StringBuilder sb = new StringBuilder();

        for (int column : columnIndexList) {
            sb.append(relation[row][column]);
        }

        hashSet.add(sb.toString());
    }

    return hashSet.size() == rowCount;
}
  1. 구한 컬럼 index를 가지고 row 만큼 반복하면서 문자열을 연결하고 hashset에 담는다.
  2. set은 중복된 값이 담기지 않으므로 중북된 값이 없다면 set size와 row의 수가 같을 것이므로 같으면 유일성안 만족한다고 판단한다.

최소성 확인

1
2
3
4
5
6
7
8
9
10
11
12
private boolean isMinimality(int set, List<Integer> list) {
    boolean isMinimality = true;

    for (int i : list) {
        if ((set & i) == i) {
            isMinimality = false;
            break;
        }
    }

    return isMinimality;
}
  1. 유일성을 만족하는 슈퍼키들(list) 중에 최소성을 만족하는 값을 찾는다.
  2. 예제에선 학번은 유일성과 최소성을 만족해서 list에 1이 추가 되지만 이름이 중복되므로 2는 유일성을 만족하지 list에 저장되지 못한다.
  3. set이 3인 경우 list에 저장된 1과 and 연산하면 11 & 1 이므로 1이 되어 1과 같으므로 최소성을 만족하지 못하고 false가 return 된다.
  4. 결국 list에 저장된 학번이 포함된 슈퍼키들은 모두 제외되고 2진수와 매핑되는 표에서 보면 {학번, 이름}(11), {학번, 전공}(101), {학번, 이름, 전공}(111), {학번 학년}(1001) … 등은 모두 제외되는 것이다.
  5. 그럼 결국 학번이 포함되지 않은 것들 중에 유일성을 만족하면서 최소성을 만족하는지 판단하게 된다.

결과

번호 속도
테스트 1 통과 (0.90ms, 50.4MB)
테스트 2 통과 (1.03ms, 51.8MB)
테스트 3 통과 (0.93ms, 51.9MB)
테스트 4 통과 (1.05ms, 52.8MB)
테스트 5 통과 (0.98ms, 52.1MB)
테스트 6 통과 (0.94ms, 50.4MB)
테스트 7 통과 (0.97ms, 50.6MB)
테스트 8 통과 (0.96ms, 52.4MB)
테스트 9 통과 (1.08ms, 50MB)
테스트 10 통과 (1.21ms, 52.3MB)
테스트 11 통과 (1.33ms, 54.7MB)
테스트 12 통과 (5.01ms, 52.9MB)
테스트 13 통과 (1.39ms, 52MB)
테스트 14 통과 (0.98ms, 54MB)
테스트 15 통과 (0.90ms, 52.5MB)
테스트 16 통과 (1.05ms, 50.8MB)
테스트 17 통과 (1.06ms, 50.5MB)
테스트 18 통과 (8.04ms, 54.5MB)
테스트 19 통과 (4.60ms, 52.9MB)
테스트 20 통과 (7.92ms, 50.5MB)
테스트 21 통과 (6.33ms, 54.7MB)
테스트 22 통과 (4.12ms, 50.7MB)
테스트 23 통과 (1.09ms, 52.7MB)
테스트 24 통과 (5.30ms, 52.5MB)
테스트 25 통과 (8.25ms, 54.4MB)
테스트 26 통과 (5.85ms, 52.3MB)
테스트 27 통과 (1.61ms, 52.8MB)
테스트 28 통과 (2.01ms, 52MB)

테스트 케이스

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
String[][] args = new String[][] {{"100","ryan","music","2"},{"200","apeach","math","2"},{"300","tube","computer","3"},{"400","con","computer","4"},{"500","muzi","music","3"},{"600","apeach","music","2"}};
assertEquals(2, test.solution(args));

String[][] args1 = new String[][] {
        {"4", "4", "사랑", "2020-07-03 오전 12:00:00", "love"}
        , {"5", "4", "같은, 좋은, 와 비슷한", "2020-07-03 오전 12:00:00", "like"}
        , {"6", "4", "사과,대도시", "2020-07-03 오전 12:00:00", "apple"}
        , {"7", "4", "빌다,기도하다,에게 간청하다", "2020-07-03 오전 12:00:00", "pray"}
        , {"8", "3", "빌다,기도하다,에게 간청하다", "2020-06-27 오전 12:00:00", "pray"}
        , {"9", "4", "안녕", "2020-07-03 오전 12:00:00", "hi"}
        , {"10", "3", "같은, 좋은", "2020-06-29 오전 12:00:00", "like"}
        , {"11", "2", "나는 모자를 벗는다", "2020-06-27 오전 12:00:00", "I take off my hat"}};

assertEquals(5, test.solution(args1));

String[][] args2 = new String[][] {
        {"4", "4", "사랑", "2020-07-03 오전 12:00:00", "love"}
        , {"5", "4", "같은, 좋은, 와 비슷한", "2020-07-03 오전 12:00:00", "like"}
        , {"6", "4", "사과,대도시", "2020-07-03 오전 12:00:00", "apple"}
        , {"7", "4", "빌다,기도하다,에게 간청하다", "2020-07-03 오전 12:00:00", "pray"}
        , {"8", "4", "빌다,기도하다,에게 간청하다", "2020-06-27 오전 12:00:00", "pray"}
        , {"9", "4", "안녕", "2020-07-03 오전 12:00:00", "hi"}
        , {"10", "3", "같은, 좋은", "2020-06-29 오전 12:00:00", "like"}
        , {"11", "2", "나는 모자를 벗는다", "2020-06-27 오전 12:00:00", "I take off my hat"}};

assertEquals(3, test.solution(args2));

참고 사이트

댓글 공유

  • page 1 of 1

Junggu Ji

author.bio


author.job