프로그래머스 - 후보키

문제

프로그래머스 - 후보키

Java 알고보기

비트 연산자

• a << b : 정수 a의 각 비트를 b만큼 왼쪽으로 이동시킨다.
  • (빈자리는 0으로 채워짐)
  • a << n : a * 2^n 과 같다.
• a >> b : 정수 a의 각 비트를 b만큼 오른쪽으로 이동시킨다.
  • (빈자리는 최상위 부호비트와 같은 값으로 채워짐)
  • a >> n : a / 2^n 과 같다.
• a >>> b : 정수 a의 각 비트를 b만큼 오른쪽으로 이동시킨다.
  • (빈자리는 0으로 채워짐)
• & 연산자 : 2진수로 표현된 두 비트가 모두 1인 경우에만 연산결과가 1로 표현됨.
• 출처 - 자바 비트연산자

Comparator 비교

• Comparator의 반환값
  • 음수 : 앞에 녀석이 작음 -> 앞에 녀석이 앞에 유지
  • 양수 : 앞에 녀석이 큼 -> 앞에 녀석이 뒤로감
  • 0 : 두 녀석이 같음
• Collections.sort : Java Doc 일부
  • 특정 Comparator 기준에 따라 정렬한다.
  • 위에서 반환값 음수/양수/0 case에 따라 정렬해줌

    Sorts the specified list according to the order induced by the specified comparator.

Iterator

• Collection Framework에서 Iterator를 구현
  • Collection Framework : List, Queue, Set
  • List에서 Iterator 메서드 사용 가능
• Iterator 메서드
  • hasNext(): 컬렉션에 다음 요소가 있는지 확인하는 메소드. 다음 요소가 있으면 true를, 없으면 false를 반환
  • next(): 컬렉션에서 다음 요소를 가져오는 메소드. hasNext()로 다음 요소가 있다는 것을 확인한 후에 next()를 호출하면 해당 요소를 반환.
  • remove(): 마지막으로 next()로 가져온 요소를 삭제하는 메소드. next()를 호출한 후에만 remove()를 호출 가능.
    

주요 흐름 - 예시 속성 4개

후보키 경우의 수 고려하기

• 총 16가지의 가능한 경우의 수 존재
  • 4가지 속성 각각이 포함 or 미포함 -> 2^4(속성 수) = 16
  • 이를 비트 연산으로 나타내면 1 << 4
  • 즉 1 << column수
• 이 중 0번째인 아무것도 없는 경우의 수 제외하고 검사

유일성 만족하는지 고려하기

• 만약 예시로 튜플 4개 있다고 했을때 비교할 수 있는 모든 경우의 수는 아래와 같음
• 한개라도 같은 튜플이 발생한다면 해당 속성은 유일성을 만족하는 것이 아님
  • A - B, C, D
  • B - C, D
  • C - D
    

최소성 만족하는지 고려하기

• 유일성 만족하는 속성의 조합들을 최소 속성 순으로 정렬
• 정렬 후 하나씩 제거한 다음 리스트의 다음 요소들에 해당 속성이 포함되어 있으면 제거
  ex) {학번}, {학번, 과목명} -> {학번, 과목명} 삭제
  

코드

import java.util.Collections;
import java.util.Comparator;
import java.util.Iterator;
import java.util.LinkedList;
import java.util.List;

class Solution {
	int rowSize;
	int colSize;
	Comparator<Integer> comp = new Comparator<Integer>() {
		int countBits(int n) {
			int ret = 0;
			while (n != 0) {
				if ((n & 1) != 0)
					++ret;
				n = n >> 1;
			}
			return ret;
		}

		@Override
		public int compare(Integer o1, Integer o2) {
			int x = countBits(o1);
			int y = countBits(o2);
			if (x > y) {
				// 양수 리턴 : 처음값이 더 큼을 의미
				return 1;
			}
			// 음수 리턴 : 오른쪽값이 더 큼을 의미
			else if (x < y)
				return -1;
			else
				return 0;
		}
	};

	boolean check(String[][] relation, int subSet) {
		// 모든 조합에 대해 값 비교
		for (int a = 0; a < rowSize - 1; a++) {
			for (int b = a + 1; b < rowSize; b++) {
				StringBuilder sbA = new StringBuilder();
				StringBuilder sbB = new StringBuilder();
				for (int k = 0; k < colSize; k++) {
					// k번째 비트를 키는것과 같다.
					// k번째 비트가 0이라면 해당 속성은 고려 대상이 아님
					if ((subSet & 1 << k) == 0) {
						continue;
					}
					// A와 B대한 해당 속성 조합 생성
					sbA.append(relation[a][k]);
					sbB.append(relation[b][k]);
				}
				// 두 튜플에 해당 조합에 해당하는 속성의 합을 비교했을떄 같으면 유일성 만족하지 않은 조합
				if (sbA.toString().equals(sbB.toString())) {
					return false;
				}
			}
		}
        // 여기 온것은 전체 튜플의 조합이 모두 다른 경우니깐 유일성 만족
		return true;
	}

	public int solution(String[][] relation) {
		int answer = 0;
		rowSize = relation.length;
		colSize = relation[0].length;
		// 1. 유일성 만족하는지 확인
		List<Integer> candidates = new LinkedList<>();
		for (int i = 1; i < 1 << colSize; i++) {
			if (check(relation, i)) {
				candidates.add(i);
			}
		}

		// 2. 속성의 개수가 적은 순으로 정렬
		Collections.sort(candidates, comp);

		// 3. 속성을 꺼냈을 때 이 속성을 포함하는 나머지 후보키를 모두 지워주면 됨
		while (candidates.size() != 0) {
			int n = candidates.remove(0);
			++answer;

			for (Iterator<Integer> it = candidates.iterator(); it.hasNext(); ) {
				int c = it.next();
				if ((n & c) == n) {
					it.remove();
				}
			}

		}
		return answer;
	}
}

전체 로직

• 유일성 만족하는지 검사
  • subSet & 1 << k : 해당 조합 번호에 해당하는 속성 bit만 검사하도록
    • ex) 학번 0001, 이름 0002
    • subSet : 1

      • k = 0 -> 1 & 1 << 0 -> 1 & 1 * 2^0 = 1 & 1 = 1
        -> if문 != 0이니 해당 속성 검사
      • k = 1 -> 1 & 1 << 1 -> 1 & 1 * 2^1 = 1 & 2 -> 01 & 10 => 00 -> continue
        ...

    • subSet : 2

      • k = 0 -> 2 & 1 << 0 -> 2 & 1 * 2^0 -> 2 & 1
        -> if문 ==0 이니 continue
      • k = 1 -> 2 & 2 << 1 -> 2 & 2 * 2^1 -> 2 & 2 -> if문 !=0 이니 해당 속성 검사
        ...

  • 유일성 비교를 위한 모든 튜플의 조합 검사 후 해당하는 조합의 번호만 리스트에 추가
    • 속성 조합 경우의 수에 포함하는 속성의 값이 튜플들 중 유일한지 검사
      ex) {학번}, {이름}, {이름, 전공}, ...의 조합이 모든 튜플에 대해 유일한지 검사
    • 속성의 조합으로 새로운 String 생성(StringBuilder 활용)

      ex) 6번 조합 : {이름, 전공}
      => 학번 200과 600번 튜플의 이름 appeach로 동일
      => 전공이 math, music으로 다름 -> {이름, 전공} 속성을 모두 보면 유일성 만족함을 조건으로 해결해야 함
      => StringBuilder로 두 문자열 합쳐서 비교해서 다름을 입증
      => appeachmath vs appeachmusic 으로 서로 다른 문자열

• 속성의 개수가 적은 순 정렬
• 속성을 꺼낸 후 해당 속성이 포함된 나머지 후보키들을 제거
  • 속성에 포함 되었는지는 &연산자 활용
  • 있는 속성이면 해당 bit가 n과 동일(n 숫자의 비트 자리수와 동일해지기 때문)

출처

• 후보키 자바 풀이
  • 유일성 검사 부분을 영상속 코드가 아닌 좀 더 직관적인 방식으로 코드 변경