[프로그래머스(Programmers)] 후보키 (java) /2019 KAKAO BLIND RECRUITMENT

3
post-thumbnail

안녕하세요! 오늘은 프로그래머스의 후보키 문제를 풀어보겠습니다. 이 문제는 2019 KAKAO BLIND RECRUITMENT에서 출제되었습니다.


1. 문제 링크

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

2. 풀이 전, 문제 이해하기

✔ 후보키의 최소성, 유일성

학번이름전공학년
100ryanmusic2
200apeachmath2
300tubecomputer3
400concomputer1
500muzimusic3
600apeachmusic2

최소성: 각각의 튜플이 유일성을 만족하는 최소의 필드 개수

표에서 학번 필드는 그 자체만으로도 유일성을 충족하며, 최소성 또한 충족합니다. {학번, 전공} 필드는 유일성을 충족하지만, 튜플이 유일성을 만족하는 최소의 필드는 학번이므로, 최소성은 충족하지 못합니다.

같은 맥락으로, 이름과 전공 필드 각각은 유일성을 충족하지 못합니다. 하지만 두 개를 합친 {이름, 전공} 필드는 유일성을 충족하며, {이름, 전공}은 튜플이 유일성을 만족하는 최소의 필드이므로 최소성 또한 충족합니다.

3. 문제 풀이

✔ dfs 수행

주어진 relation의 column으로 dfs를 수행해줍니다. 이 때 {0,1}과 {1,0}을 같은 경우로 생각해서 dfs코드를 짜면 됩니다.

✔ dfs 수행 완료될 때마다 column index 최소성 여부 확인

dfs 수행 후 column index 쌍이 완성될 때마다 해당 column index가 최소성을 충족하는지를 확인해줍니다.

✔ 최소성 충족 시 유일성 충족 여부 확인

column index가 최소성을 충족한다면, 유일성까지 충족하는지를 확인합니다. 유일성까지 모두 충족하면 answer값을 하나 증가시키고, 해당 키의 column index쌍을 list에 저장합니다.

메서드들의 순서를 그림으로 표현하면 이렇게 됩니다

4. 전체 코드

import java.util.*;

class Solution {
    private int row;
    private int col;
    private int answer;

    private int[] keyDfs;		//column을 dfs 돈 결과들
    private boolean[] visited;
    private String[][] relationStr;	//주어진 relation
    private List<String> uniqueKeyList;	//unique Key인 column 저장

    public int solution(String[][] relation) {
        answer = 0;
        row = relation.length;
        col = relation[0].length;
        relationStr = relation;
        uniqueKeyList = new ArrayList<>();

        for (int i = 1; i <= col; i++) {
            keyDfs = new int[i];
            visited = new boolean[col];

            keyColumnDfs(i, 0, 0);
        }

        return answer;
    }

    //howMany, index, at, col(size)
    private void keyColumnDfs(int howMany, int index, int at) {
        if (howMany == index) {
            if (!isAlreadyMinKey()) {
                uniqueKeyCheck();
            }
            return;
        }

        for (int i = at; i < col; i++) {
            if (!visited[i]) {
                visited[i] = true;
                keyDfs[index] = i;
                keyColumnDfs(howMany, index + 1, i);
                visited[i] = false;
            }
        }
    }

    //row, keyDfs, answer, relationStr, uniqueKeyList
    private void uniqueKeyCheck() {
        Set<String> keyString = new HashSet<>();
        StringBuilder sb;

        for (String[] arr : relationStr) {
            sb = new StringBuilder();

            for (int num : keyDfs) {
                sb.append(arr[num].toString());
            }
            keyString.add(sb.toString());
        }

        if (keyString.size() == row) {
            answer += 1;
            uniqueKeyList.add(keyDfsToString());
        }
    }
    
    //후보키 최소성 체크
    //keyDfs, uniqueKeyList 비교
    //keyDfs가 uniqueKeyList의 값들을 전부 contain하고 있으면 -> 최소성 만족 X
    private boolean isAlreadyMinKey() {
        if (uniqueKeyList.isEmpty()) {
            return false;
        }

        List<Integer> keyDfsList = new ArrayList<>();

        for (int num : keyDfs) {
            keyDfsList.add(num);
        }

        for (String ukl : uniqueKeyList) {
            List<Integer> uniqueKey = new ArrayList<>();

            String[] array = ukl.split("");
            for (String str : array) {
                int num = Integer.parseInt(str);
                uniqueKey.add(num);
            }
            
            if (keyDfsList.containsAll(uniqueKey)) {
                return true;
            }
        }

        return false;
    }

    //keyDfs -> String 변환
    private String keyDfsToString() {
        StringBuilder sb = new StringBuilder();

        for (int num : keyDfs) {
            sb.append(num);
        }

        return sb.toString();
    }
}

5. 느낀점

예전에 한 번 풀었었는데, 코드가 너무 이상해서 따로 포스팅하지 않았던 문제였다. 시간이 한참 지나서 다시 풀어보니 그 때 왜 그렇게 어렵고 복잡하게 풀었을까 싶다. 함수의 순서를 먼저 생각해보고(그림을 그려보면 효과적임) 문제를 풀면 더 체계적으로 풀이를 작성할 수 있다. 이전에는 그러지 않고 주먹구구식으로 급하게 생각해서 더 이상하게 풀었던 것 같다.

✔ 최소성 만족여부 확인 메서드 어려웠음

최소성을 만족하는지 확인하는 함수의 구현이 좀 어려웠다. uniqueKeyList에 unique key의 column들을 저장해두는데 list에 저장된 string을 split해서 int로 바꿔서 비교하는 형변환과정이 너무 귀찮았고 복잡했다.

0개의 댓글