[프로그래머스] 후보키

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

코딩테스트 연습 - 후보키

카카오 블라인드 테스트에서 출제된 문제이고, 프로그래머스 기준 레벨 2 문제입니다.

문제 해결 방식으로 칼럼들의 조합으로 나온 결과물의 중복 여부를 자료구조 set 을 활용해서 체크하고,

만약 중복이 되지 않는다고 가정할 때 최소성까지 있는지를 체크한 다음 최소성을 보유하고 있다면 answer 값에 추가해서 리턴하면 되는 문제입니다.

 

중복 여부 체크 후 중복이 되지 않는 경우, 최소성 체크할 때 부분집합 비교 과정에서 2진수를 활용하면 도움이 됩니다!

 

예제 코드는 다음과 같습니다.

import java.util.*;
import java.util.stream.Collectors;
class Solution {
    public static int solution(String[][] relation) {
        int answer = 0;
        int rowCount = relation.length;
        int colCount = relation[0].length;
        List<Integer> list = new ArrayList<>();        
        for (int i = 1; i < (1 << colCount); i++) {
            int temp = i;
            int index = 0;
            boolean[] check = new boolean[colCount];

            while(temp > 0) {
                if (temp % 2 > 0) check[index] = true;
                temp >>= 1;
                index++;
            }
            // 칼럼 집합 계산
            Set<String> set = new HashSet<>();
            for (int j = 0; j < rowCount; j++) {
                String elem = "";
                for (int k = 0; k < colCount; k++) {
                    if (check[k] == true) {
                        elem += relation[j][k];
                    }
                }
                set.add(elem);
            }
            // 중복이 없는 경우
            if (rowCount == set.size()) {
                boolean isExist = false;
                // 최소성을 만족하는지 체크 (isExist = false -> 최소성 만족)
                for (int j = 0; j < list.size(); j++) {
                    int val = list.get(j);
                    if ((val & i) == val) {
                        isExist = true;
                    }
                }
                if (!isExist) {
                    list.add(i);
                }
            }
        }
        return list.size();
    }
}