(2018카카오) 후보키 Java

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

 

일반적인 탐색문제이다..DFS방식도 있지만 완전탐색이 더 실행속도 측면에서 빨랐다.

 

하지만 Bit Mask방식으로 For문으로 경우의수를 나눠서 풀 수 있다.

BitMask방식은 이진법을 이용하여 0=000(2) ~ 15=111(2) 으로 001, 010, 011, ... , 110, 111 방식으로 

 

https://keepgoing0328.tistory.com/entry/%ED%94%84%EB%A1%9C%EA%B7%B8%EB%9E%98%EB%A8%B8%EC%8A%A4-2019-%EC%B9%B4%EC%B9%B4%EC%98%A4-%EA%B3%B5%EC%B1%84-%ED%9B%84%EB%B3%B4%ED%82%A4-%EC%9E%90%EB%B0%94-bitmask

[ 프로그래머스 - 2019 카카오 공채 ] 후보키 ( 자바, bitmask )

 

아래는 완전탐색 풀이다. 문자열을 비교할때 콤마를 넣어주는것이 원칙적으로 올바른 비교다.

import java.util.ArrayList;
import java.util.HashSet;
import java.util.Set;


class Solution {
​​​​public int solution(String[][] relation) {
​​​​​​​​int n = relation.length;        // n개의 데이터
​​​​​​​​int m = relation[0].length;     // m개의 컬럼
​​​​​​​​ArrayList<Integer> list = new ArrayList<Integer>();

​​​​​​​​// 완전 탐색을 돈다.
​​​​​​​​for(int i=1; i<(1<<m); i++) {
​​​​​​​​​​​​Set<String> s = new HashSet<String>();
​​​​​​​​​​​​// n개의 데이터
​​​​​​​​​​​​for(int j=0; j<n; j++) {
​​​​​​​​​​​​​​​​String now = "";
​​​​​​​​​​​​​​​​// m개의 컬럼
​​​​​​​​​​​​​​​​for(int k=0; k<m; k++) {
​​​​​​​​​​​​​​​​​​​​// 모든 경우의 수 & 해당 라인 데이터 조합.
​​​​​​​​​​​​​​​​​​​​if( (i&(1<<k)) > 0 ) {
​​​​​​​​​​​​​​​​​​​​​​​​now+="," + relation[j][k];
​​​​​​​​​​​​​​​​​​​​}
​​​​​​​​​​​​​​​​}
​​​​​​​​​​​​​​​​s.add(now);
​​​​​​​​​​​​}
​​​​​​​​​​​​if(s.size()==n&&possi(list,i)) list.add(i);
​​​​​​​​}
​​​​​​​​//System.out.println(list.size());
​​​​​​​​return list.size();
​​​​}
​​​​public static boolean possi(ArrayList<Integer> list, int now) {
​​​​​​​​for(int i=0; i<list.size(); i++) {
​​​​​​​​​​​​// 같으면 최소성을 만족하지 못함.
​​​​​​​​​​​​if((list.get(i)&now)==list.get(i)) {
​​​​​​​​​​​​​​​​return false;
​​​​​​​​​​​​}
​​​​​​​​}
​​​​​​​​return true;
​​​​}
}

 

dfs방식이다.

import java.util.*;

class Solution {
​​​​public int solution(String[][] relation) {
​​​​​​​​candidates = new ArrayList<HashSet<Integer>>();

​​​​​​​​select(0, new HashSet<Integer>(), relation);
​​​​​​​​return candidates.size();
​​​​}

​​​​static ArrayList<HashSet<Integer>> candidates;

​​​​// select() : column에 대한 모든 부분 집합을 만든다. 하나의 부분 집합(selects)이 만들어지면, 후보키인지 검사 후 candidates에 추가한다.
​​​​// column에서 pos 번째 열, selects: dfs에서 만들어지는 부분 집합
​​​​static void select(int pos, HashSet<Integer> selects, String[][] relation) {

​​​​​​​​if (pos == relation[0].length) {

​​​​​​​​​​​​// 만들어진 selects가 다른 후보키를 포함하나
​​​​​​​​​​​​for (int i = 0; i < candidates.size(); i++) {
​​​​​​​​​​​​​​​​if (selects.containsAll(candidates.get(i))) {
​​​​​​​​​​​​​​​​​​​​return;
​​​​​​​​​​​​​​​​}
​​​​​​​​​​​​}

​​​​​​​​​​​​// selects가 유일성을 만족하나
​​​​​​​​​​​​HashSet<String> sets = new HashSet<String>();
​​​​​​​​​​​​for (int row = 0; row < relation.length; row++) {
​​​​​​​​​​​​​​​​String temp = "";
​​​​​​​​​​​​​​​​for (int col : selects) {
​​​​​​​​​​​​​​​​​​​​temp += relation[row][col] + ",";
​​​​​​​​​​​​​​​​}
​​​​​​​​​​​​​​​​if (sets.contains(temp)) {
​​​​​​​​​​​​​​​​​​​​return;
​​​​​​​​​​​​​​​​}
​​​​​​​​​​​​​​​​sets.add(temp);
​​​​​​​​​​​​}

​​​​​​​​​​​​// 추가!
​​​​​​​​​​​​candidates.add(selects);
​​​​​​​​​​​​return;
​​​​​​​​}

​​​​​​​​// call by value 이기 때문에 copy, copy2
​​​​​​​​HashSet<Integer> copy = new HashSet<Integer>();
​​​​​​​​HashSet<Integer> copy2 = new HashSet<Integer>();
​​​​​​​​for (Integer val : selects) {
​​​​​​​​​​​​copy.add(val);
​​​​​​​​​​​​copy2.add(val);
​​​​​​​​}

​​​​​​​​select(pos + 1, copy2, relation);
​​​​​​​​copy.add(pos);
​​​​​​​​select(pos + 1, copy, relation);


​​​​}
}