[프로그래머스] 후보키

 

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

코딩테스트 연습 - 후보키

 

내 풀이

문제를 사실 제대로 풀어내지 못했다. 하지만 오늘 내가 생각했던 접근 방식이 크게 틀리지는 않았기에 나중에 다시 풀어보고자 한다. 

우선 

조건이 최소성과 유일성 이 있고, 이를 만족하는 후보키의 개수를 구하는 것이 목적이였다

(지금 다시 보니 최소성의 의미를 잘못 이해하여 헤맸던 것 같다

최소성은 꼭 필요한 속성들로만 구성이되어야 한다는 의미였다

나는 이것을 유일성을 지키는 최소한의 키의 개수를 구하라는 의미인 줄 알았다... )

 

이를 구하기 위해서는 조합으로 N 개중 1개를 뽑는 경우.... 2개를 뽑는 경우... 로 늘려나가면서 유일성을 만족하는 후보키를 찾으면 멈추고 후보키의 개수를 반환하는 방향으로 접근하였다.

(문제를 제대로 이해하지 못하여 발생한 잘못된 접근)

 

근데 유일성을 체크하는 과정에서도 괜찮은 방법이 생각나지 않고 그렇다고 무식하게 검사하자니 시간 초과가 날 것 같고, 아니여도 성이 차지 않아 고민하다보니 처음 내가 생각했던 접근 자체가 틀렸나 의심이 들고 다른 좋은 방법이 있나 싶어 검색해보았다.

 

[프로그래머스] 후보키 (Java) (velog.io)

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

 

 

 

이 분의 풀이를 보고 내가 문제를 잘못 이해하고 있었던 부분이랑 생각하지 못한 유일성을 체크하는 좋은 방법을 배워갈 수 있었다. 

 

 

import java.util.*;

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

        int rowLen = relation.length;
        int colLen = relation[0].length;

        //비트마스킹으로 모든 경우의 조합 시도
        for(int set = 1 ; set < (1 << colLen) ; set++) {
            // 최소성 검사
            if(!isMinimal(set, candidateKey))
                continue;

            // 유일성 검사
            if(isUnique(set, rowLen, colLen, candidateKey, relation)) {
                //System.out.println(Integer.toBinaryString(set));
                candidateKey.add(set);
            }
        }

        return candidateKey.size();
    }
    
    private static boolean isUnique(int set, int rowLen, int colLen, ArrayList<Integer> candidateKey, String[][] relation) {
        HashMap<String, String> map = new HashMap<>();

        //자릿수 구하기
        for(int row = 0 ; row < rowLen ; ++row) {
            String dataByKeySet = "";

            for(int th = 0 ; th < colLen ; ++th) {
                //set과 같다면 dataByKeySet에 추가
                if((set & (1 << th)) != 0) {
                    dataByKeySet += relation[row][th];
                }
            }

            //이미 있다면 => 유일성 깨기에 false
            if(map.containsKey(dataByKeySet))
                return false;
            //없다면 유일성 지킴, hashmap에 저장
            else
                map.put(dataByKeySet, dataByKeySet);
        }

        return true;
    }

    private static boolean isMinimal(int set, ArrayList<Integer> candidateKey) {
        //이미 후보키에 선정된 조합이 들어있다면 최소성을 깸
        for(int key : candidateKey) {
            //포함관계 구하기
            if((key & set) == key)
                return false;
        }

        return true;
    }
    
}