(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);


    }
}