[JAVA] 프로그래머스 후보키

1) 문제

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

2) 접근 방법

헉쓰.. 어려워서 결국 다른 분의 풀이/설명을 보면서 이해했다...

출처 :
https://middleearth.tistory.com/62
https://www.youtube.com/watch?v=-QQ18ZA7qrc&t=678s

각 컬럼을 하나의 비트로 생각하면,

0000 → 아무것도 없는 거니까 공집합
0001 → 학번만 있는 경우..
=> 0부터 1씩 값을 더하면, 비트가 하나씩 꺼지고 켜짐으로써 모든 부분집합을 구할 수 있게 된다.

부분집합은 0부터 시작하는데,
1을 원소의 개수(4)만큼 시프트 시키면 10000이 된다.
1 << 4 = 10000 -> 16

• 1 << : 주어진 숫자를 비트로 펴주는 동시에 + 1 해준다는 의미

for문으로 이것보다 작은 값에 대해 순회를 돌면 인덱스 배열의 값이 0 ~ 15까지 가게 된다.

• 공집합 부터 시작할 필요는 없으니까 0이 아니라 1부터 시작하면 됨

후보키가 될 수 있는 이 경우의 수 후보들이 유일성/최소성 을 만족하는지 확인해봐야 한다.

• 유일성을 만족하는지 확인
  • outer loop : m개 컬럼에 대한 경우의 수(0001, 0010...)에 대해 확인
    • set을 만든다.
    • inner loop : 튜플들에 대해 확인
      • 더 안쪽 inner loop :
        튜플에서 컬럼들을 돌면서, if((i & 1 << k) > 0) 를 통해 i의 k번째 비트가 켜져있는지를 확인해 본다.
      • set에 해당 경우의 수를 넣는다.
    • set의 사이즈가 튜플의 수와 일치하는지 확인한다 -> 같아야지만 모두 유일하게 구별된 것임!
• 최소성을 만족하는지 확인
  • 현재의 비트(i)를 받고, 정답 리스트를 돌면서 if ((i & j) == j) return false;로 부분집합 여부를 체크
  • ex)
    i = 111, j = 011
    -> i & j = 011
    -> j가 i의 부분집합이 되므로 false

3) 코드

import java.util.*;

class Solution {
    // 비트를 담는 list
    List<Integer> answer = new ArrayList<>();
    
    public int solution(String[][] relation) {
        int n = relation.length; // 튜플 개수
        int m = relation[0].length; // 컬럼 개수
        
        // 조합 만들기
        for (int i = 1; i < 1 << m; i++) { // m개 컬럼에 대한 경우의 수(0001, 0010...)
            Set<String> set = new HashSet<>(); // 
            
            // 튜플들을 다 확인
            for (int j = 0; j < n; j++) {
                String temp = "";
                // 튜플에서 컬럼들을 돌면서 확인
                for (int k = 0; k < m; k++) {
                    if ((i & 1 << k) > 0) { // i의 k번째 비트가 켜져있는지(1) 확인
                        temp += (relation[j][k]);
                    }
                }
                set.add(temp);
            }
            
            // 유일성을 만족하고 최소성을 만족한다면
            if (set.size() == n && check(i)) {
                answer.add(i);
            }
        }
        
        return answer.size();
    }
    
    // 최소성 확인
    boolean check(int i) {
        for (int j : answer) {
            if ((i & j) == j) // i & j == j 의 의미 : i가 j의 부분집합인지 여부
                // ex : i = 111, j = 011 -> i & j = 011 -> j가 i의 부분집합이 되므로 false
                return false;
        }
        return true;
    }
}

느낀 점

와 짱 어렵다.. 열심히 공부해서 어렵게 느껴지는 문제들도 잘 풀어내고 싶다...!!