[Algorithm] 프로그래머스 2019 카카오 공채 - 후보키 (비트마스크)

문제

 

프로그래머스 2019 카카오 공채 - 후보키

코딩테스트 연습 - 후보키

뭔가 간단해보이고 자료구조를 이용해 어떻게 해낼 수 있을 것 같았는데, 

'비트마스크'라는 새로운 풀이법을 적용해야 했다.

 

---

풀이

1. for문을 돌려 인덱스의 부분집합을 구해 해당 부분집합의 인덱스 조합이 후보키가 될 수 있는지를 검사한다.
   
   • 1을 colSize만큼 왼쪽으로 쉬프트하게 되면 2^colSize이므로 이는 인덱스 부분집합의 개수를 의미한다
   • i를 2진수로 변환하면 인덱스의 부분집합이 된다
   • 왼쪽부터 집합의 i번째 요소가 존재한다면 1, 아니면 0을 뜻한다
     • 1 = 0001 = {0}
     • 2 = 0010 = {1}
     • 3 = 0011 = {0, 1}
     • 4 = 0100 = {2}
     • ...
     • 15 = 1101 = {0, 2, 3}
     • 16 = 1111 = {0, 1, 2, 3}
2. 후보키의 첫번째 조건인 최소성을 만족하는지 검사한다
   
   • 만약 '학번'이 후보키로 이미 결과 리스트에 포함되어 있다면 '학번'을 포함하고 있는 부분 집합은 후보키가 될 수 없다. 이미 '학번'만으로 튜플을 식별할 수 있기 때문이다
   • if((arr & key) == key) -> AND 연산자를 사용하면 두 비트가 모두 1일 때만 1을 반환하므로 현재 검사 중인 부분 집합이 결과 리스트에 포함되어 있는지 확인할 수 있다
3. 후보키의 두번째 조건인 유일성을 만족하는지 검사한다
   • 정수로 나타낸 부분집합을 다시 인덱스의 조합으로 바꾼다
   • if(((arr >> i)&1)==1) list.add(i); -> 2진수를 한자리씩 오른쪽으로 쉬프트하며 1과 AND연산자를 수행했을 때 값이 1이라면 해당 인덱스가 부분집합에 포함되어 있음을 확인할 수 있다
     • (0111 & 0001)=0001 -> 1과 &한 결과가 1이므로 0번 인덱스가 부분집합에 포함되어 있다
     • (0011 & 0001)=0001 -> 1번 인덱스가 부분집합에 포함되어 있다
     • (0001 & 0001)=0001 -> 2번 인덱스가 부분집합에 포함되어 있다
     • (0000 & 0001)=0000 -> 3번 인덱스는 부분집합에 포함되어 있지 않다
   • 구한 인덱스의 값들을 StringBuilder에 이어붙혀 문자열을 만들고, 중복을 허용하지 않는 set를 이용해 유일성 검사를 수행한다
4. 구한 부분집합의 갯수가 바로 정답!

public static int solution(String[][] relation) {
		int rowSize = relation.length, colSize = relation[0].length;
		ArrayList<Integer> result = new ArrayList<Integer>();
		
		// 1. 인덱스의 부분집합을 구해 후보키인지 확인
		for (int i = 1; i < (1<<colSize); i++) { // (1<<colSize)=부분집합의 개수
			if(!isMinimal(i, result)) continue;
			if(!isUnique(i, relation, rowSize, colSize)) continue;
			
			result.add(i);
		}

		return result.size();
	}
	
	// 2. 결과 리스트에 이미 들어간 키가 현재 부분집합에 포함되어 있는지 최소성 검사
	static boolean isMinimal(int arr, ArrayList<Integer> result) {
		for(int key : result) 
			if((arr & key)==key) return false; // 중복이면 false
		return true;
	}

	// 3, 부분 집합에 포함된 인덱스들이 후보키가 될 수 있는지 유일성 검사
	static boolean isUnique(int arr, String[][] relation, int rowSize, int colSize) {
		ArrayList<Integer> s = convertToIdx(arr, colSize);
		HashSet<String> set = new HashSet<>();
		
		for (int i = 0; i < rowSize; i++) {
			StringBuilder sb = new StringBuilder();
			for (int j : s) sb.append(relation[i][j]);
			set.add(sb.toString());
		}
		
		return set.size() == rowSize;
	}
	
	// 이진수를 인덱스로 바꿔주는 함수
	static ArrayList<Integer> convertToIdx(int arr, int colSize){
		ArrayList<Integer> list = new ArrayList<Integer>();
		
		for(int i=0; i<colSize; i++)
			if(((arr>>i)&1)==1) list.add(i);
		
		return list;
	}