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

후보키

문제

---

문제 설명

테이블의 정보가 String[][] relation 형태로 주어졌을 때 이 테이블에서 나올 수 있는 후보 키의 최대 개수를 구하는 문제이다.

---

구현

비트마스킹 문제를 풀려고 찾은 문제여서 비트마스킹으로 접근했다.

코드를 짜기 전 생각한 구현 단계는
1. 비트마스킹으로 나올 수 있는 컬럼들의 조합을 생성 ( O(2^colNum) )
2. 컬럼들의 조합이 나왔다면 그 컬럼들을 조합해서 HashSet에 넣기 ( O(rowNum * colNum) )
3. 만약에 HashSet의 크기가 Rownum의 크기가 같다면 유일성을 만족하게 되니깐 최소성을 파악하자.
4. 정답을 담아두는 HashSet의 조합들과 & 연산을 했을 때 기존에 등록된 키와 같다면 최소성을 만족시키지 못하기 때문에 정답 HashSet에 넣지 않는다. ( O(2^colNum) )

이렇게 생각하는데 한 20분 정도가 걸린 것 같다.

시간복잡도 계산에서는 1번 단계안에서 2, 3, 4 번의 과정을 모두 해야하기 때문에 rowNum을 N, colNum을 M 으로 보면
총 시간복잡도는 O(2^m n m + 2^(2m)) 이정도 된다.

딱 봐도 너무 커서 걱정했는데 문제에서 M이 8이하, N이 20 이하여서 생각보다 그렇게 크지 않아서 그대로 구현했다.

그리고 그렇게 구현을 하는데에 20분 걸렸다.

1. 컬럼 조합 생성

일단 컬럼을 정할 때 사용할 mask 변수를 colNum 만큼 leftShift 한만큼 반복해준다.

//어떤 컬럼을 고를지 비트마스킹으로 결정
for(int mask = 1; mask < (1 << colNum); mask++) {
	//이번에 뽑힌 컬럼들로 set 생성
	HashSet<String> set = new HashSet<>();
    
	//구현
}

2. 컬럼들을 조합해서 HashSet에 넣기

이제 유일성을 식별하기 위해 선택된 컬럼들로 조합한 문자열을 HashSet에 넣어줘야한다.
각 줄별로 해야하기 때문에 rowNum 만큼 반복하는 반복문 내에 StringBuilder 로 문자열을 생성해 줄것이다.

이제 각 row에서 각 column들을 방문해주며 이번에 조합된 mask의 값에 column이 해당되면 StringBuilder에 넣어주고 모든 column을 다 돌면 set에 넣어준다.

//어떤 컬럼을 고를지 비트마스킹으로 결정
for(int mask = 1; mask < (1 << colNum); mask++) {
	//이번에 뽑힌 컬럼들로 set 생성
	HashSet<String> set = new HashSet<>();
    
	//컬럼은 골랐으니 그것들로 유일성을 가지는지 식별
    for(int i = 0; i < rowNum; i++){
		StringBuilder sb = new StringBuilder();
		for(int j = 0; j < colNum; j++){
			if((mask & (1 << j)) != 0){
				sb.append(relation[i][j]).append(" ");
			}
		}
		set.add(sb.toString());
	}
    
    //구현
}

3. 유일성 판별과 최소성 판단

만약에 위에서 반복해서 나온 set의 크기와 rowNum이 같다면 유일성이 만족 된거니깐 이제 최소성을 판단해보자.

현재까지의 후보키들을 저장한 candidateSet 이라는 HashSet에 있는 숫자를 candidateKey 라고 했을 때 이번에 지정된 mask의 값과 candidateKey 를 & 연산한 값이 기존에 있던 candidateKey와 같다면 해당 키는 최소성을 만족시키지 못하기 때문에 후보키가 될 수 없다.

이걸 구현하기 위해서 flag 변수를 두고 만약에 같다면 flag 를 false 로 초기화하고 루프를 빠져나오는 식으록 구현했다.

if(set.size() == rowNum){
//mask & candidateSet 를 비교하여 candidateSet에 추가
	boolean flag = true;
	for(int candidateKey : candidateSet){
		if ((candidateKey & mask) == candidateKey){
			flag = false;
            break;
		}
	}
                
	if(flag){
		candidateSet.add(mask);
	}
} else continue;

---

코드

import java.util.*;

class Solution {
    public int solution(String[][] relation) {
        //최종 후보키를 넣을 HashSet
        HashSet<Integer> candidateSet = new HashSet<>();
        int answer = 0;
        
        int rowNum = relation.length;
        int colNum = relation[0].length;
        
        //어떤 컬럼을 고를지 비트마스킹으로 결정
        for(int mask = 1; mask < (1 << colNum); mask++) {
            HashSet<String> set = new HashSet<>();
            //컬럼은 골랐으니 그것들로 유일성을 가지는지 식별
            for(int i = 0; i < rowNum; i++){
                StringBuilder sb = new StringBuilder();
                for(int j = 0; j < colNum; j++){
                    if((mask & (1 << j)) != 0){
                        sb.append(relation[i][j]).append(" ");
                    }
                }
                set.add(sb.toString());
            }
            //유일성을 가지면 최소성 판단, 그렇지 않으면 넘기기
            if(set.size() == rowNum){
                //mask & candidateSet 를 비교하여 candidateSet에 추가
                boolean flag = true;
                for(int candidateKey : candidateSet){
                    if ((candidateKey & mask) == candidateKey){
                        flag = false;
                        break;
                    }
                }
                
                if(flag){
                    candidateSet.add(mask);
                }
            } else continue;
        }
        
        answer = candidateSet.size();
        
        return answer;
    }
}