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

Question

• 문제 링크 : https://programmers.co.kr/learn/courses/30/lessons/42890
• 분류 : 완전탐색(브루트포스)
• 풀이 시간 : 120분

문제 해설

1. 여러 컬럼 중에서 후보키를 뽑으려고 함
   • 후보키로 row를 유일하게 식별할 수 있어야 함 : 유일성
   • 유일하게 값을 식별할 수 있는 조합 중 최소한의 조합이여야 함 : 최소성
2. 후보키의 개수는?

Solution

풀이 접근 방법

1. 모든 컬럼의 조합을 구함
2. 조합 중 유일성 만족하는 조합 고르기
3. 그 중 최소성 만족하는 조합만 저장
   • 여태껏 나왔던 후보키 조합을 포함하지 않는 조합만 저장

정답 코드

package com.programmers.bp;

import java.util.HashSet;

public class CandidateKey {
  static int rows, columns;
  static String[][] table;
  static HashSet<HashSet<Integer>> candidate;

  public int solution(String[][] relation) {
    rows = relation.length;
    columns = relation[0].length;
    table = relation;
    candidate = new HashSet<HashSet<Integer>>();

    for (int pick = 1; pick <= columns; pick++) {
      getKeySet(0, pick, new HashSet<Integer>());
    }

    return candidate.size();
  }

  /**
   * 키의 조합을 구하는 함수
   * start : 키 집합 안에 넣을 다음 값
   * pick : 뽑아야할 개수
   * set : 뽑은 컬럽 조합 집합
   **/
  public void getKeySet(int start, int pick, HashSet<Integer> set) {
    if (pick == 0) {

      // 유일성을 만족하지 않으면 후보키 될 수 없음
      if (!isUnique(set))
        return;

      // 이미 뽑힌 후보키에서 최소성 확인
      for (HashSet<Integer> part : candidate) {
        HashSet<Integer> temp = new HashSet<>(part);
        
        // 기존의 후보키 조합 - 뽑힌 후보키 조합
        temp.removeAll(set);

        // = 0
        // 뽑힌 후보키 조합이 기존의 조합을 포함하고 있음
        if (temp.size() == 0)
          return;
      }

      candidate.add(set);

      return;
    }

    for (int i = start; i < columns; i++) {
      HashSet<Integer> newSet = new HashSet<Integer>(set);
      newSet.add(i);
      getKeySet(i + 1, pick - 1, newSet);
    }
  }

  /**
   * 키의 조합이 유일성을 만족하는지 확인하는 함수
   **/
  public boolean isUnique(HashSet<Integer> set) {
    HashSet<String> setResult = new HashSet<String>();

    for (String[] row : table) {
      String value = "";

      for (Integer idx : set) {
        value += row[idx];
      }
      
      // 겹치는 값이 하나라도 있으면 값들을 유일하게 식별해낼 수 없음
      if (!setResult.add(value))
        return false;
    }

    return true;
  }
}

알.쓸.유.메(알아두면 쓸데있는 유용한 메소드)

집합 연산 메소드

HashSet<T> hashSet = new HashSet<T>();

hashSet.addAll(set1);	// 합집합 : set1에 들어있는 값 다 hashSet에 넣음
hashSet.removeAll(set2);	// 차집합 : set2에 들어있는 값 다 hashSet에서 삭제
hashSet.retainAll(set3);	// 교집합 : set과 set3와 공통된 부분만 남김