[PGM_42890] 후보키 (java)

문제링크

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

코딩테스트 연습 - 후보키

문제풀이

👨🏻‍💻 핵심 스킬 👨🏻‍💻
 완전탐색

1. 문제 이해

DB에 대한 릴레이션이 주어지면 그에 해당하는 후보키가 총 몇개가 존재하는지 찾아내는 문제이다.

 

2. 접근방법

1) 재귀를 활용하여 키가 될 수 있는 조합을 구해준다.

2) 구한 조합이 슈퍼키인지 확인한다.

3) 슈퍼키를 모두 구해주었다면 후보키로 변경한다.

4) 구해진 후보키의 길이를 반환해준다.

 

3. 구현코드 추가설명

Set<String> check = new HashSet<>();
for(int i = 0; i < relation.length; i++){
    // 튜플 구하여 슈퍼키인지 확인
    String tuple = "";
    for(int j = 0; j < relation[i].length; j++){
        if(used[j])
            tuple += relation[i][j];
    }
    if(check.contains(tuple))
        return;
    if(tuple.equals(""))
        return;
    check.add(tuple);
}

슈퍼키 후보에 대하여 체크를해주는 과정이다. 튜플들이 중복되는지 확인하기 위해 Set을 활용하였다. 만들어진 튜플을 Set에 넣어주는데, 만약 값이 있다면 중복되는 것 이므로 슈퍼키가 아니라고 판단하였다.

 

int count = keys.stream()
        .filter((s) -> {
            //각 문자들로 순회하며 확인
            for (int i = 0; i < infoAboutKey.length; i++) {
                boolean isContain = true;
                for(int j = 0; j < infoAboutKey[i].length(); j++){
                    if(!s.contains(infoAboutKey[i].charAt(j) +"")) {
                        isContain = false;
                        break;
                    }
                }
                if (isContain && !s.equals(infoAboutKey[i]))
                    return false;
            }
            return true;
        }).collect(Collectors.toList()).size();

구해진 슈퍼키들로 후보키를 찾아주는 과정이다. 후보키는 슈퍼키 중에 최소성을 만족하는 것이다. 모든 슈퍼키에 대하여 특정 키를 포함하는지 체크하여주기 위해 문자단위로 비교를 해주었다. 만약 포함된다면 슈퍼키이지만 후보키가 아니므로 배제해주는 코드이다.

구현코드

import java.util.HashSet;
import java.util.Set;
import java.util.stream.Collectors;

public class Solution {
    public int solution(String[][] relation) {

        boolean[] used = new boolean[relation[0].length];
        Set<String> keys = new HashSet<>();
        makeKeyRecursive(0,used, relation, keys);

        String[] infoAboutKey = keys.toArray(new String[0]);
        int count = keys.stream()
                .filter((s) -> {
                    //각 문자들로 순회하며 확인
                    for (int i = 0; i < infoAboutKey.length; i++) {
                        boolean isContain = true;
                        for(int j = 0; j < infoAboutKey[i].length(); j++){
                            if(!s.contains(infoAboutKey[i].charAt(j) +"")) {
                                isContain = false;
                                break;
                            }
                        }
                        if (isContain && !s.equals(infoAboutKey[i]))
                            return false;
                    }
                    return true;
                }).collect(Collectors.toList()).size();
        return count;
    }

    /**
     * 완전 탐색
     * @param point 칼럼을 사용할지 말지 고르는 포인터
     * @param used 사용하는 칼럼 = true, 사용 안하는 칼럼 = false
     * @param relation 주어진 relation
     * @param keys 슈퍼키
     */
    public void makeKeyRecursive(int point, boolean[] used, String[][] relation , Set<String> keys){
        if(point == relation[0].length){
            Set<String> check = new HashSet<>();
            for(int i = 0; i < relation.length; i++){
                // 튜플 구하여 슈퍼키인지 확인
                String tuple = "";
                for(int j = 0; j < relation[i].length; j++){
                    if(used[j])
                        tuple += relation[i][j];
                }
                if(check.contains(tuple))
                    return;
                if(tuple.equals(""))
                    return;
                check.add(tuple);
            }

            // 슈퍼키 일 경우
            String key = "";
            for(int i = 0; i < used.length; i++){
                if(used[i])
                    key += i;
            }
            keys.add(key);
            return;
        }

        //재귀로 돌며 모든 경우를 탐색
        makeKeyRecursive(point+1,used,relation,keys);
        used[point] = true;
        makeKeyRecursive(point+1,used,relation,keys);
        used[point] = false;
    }
}

잘못된 지식이나 궁금한 내용이 있을 경우 편하게 댓글 남겨주시면 감사하겠습니다 :)