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

문제 설명

 

프로그래머스

 

접근 방법

해당 문제는 특정 테이블 형태의 데이터가 주어졌을 때 유일성과 최소성을 만족하는 후보키의 개수를 요구하고 있습니다.

 

접근 방법으로는 우선 백트래킹을 통해 모든 키에 대한 경우의 수를 구하도록 했습니다. 이때 키의 칼럼 수는 최소 1개에서 최대 릴레이션 상 전체 칼럼 수의 개수(n)와 같습니다. 1개부터 n개까지 순차적으로 백트래킹을 하면서 경우의 수가 만들어지면 해당 키에 대해 유일성과 최소성을 검증(verify 메서드 호출)하도록 했습니다.

 

    // ...

        boolean[] visited;

        for (int i = 1; i <= columnTotalCount; i++) {
            visited = new boolean[columnTotalCount];
            findForeignKey(0, 0, i, visited);
        }
        
    // ...

    private void findForeignKey(int depth, int choiceCount, int columCount, boolean[] visited) {
        if (choiceCount == columCount) {
            verify(visited);
            return;
        }

        if (depth == columnTotalCount) {
            return;
        }

        visited[depth] = true;
        findForeignKey(depth + 1, choiceCount + 1, columCount, visited);
        visited[depth] = false;
        findForeignKey(depth + 1, choiceCount, columCount, visited);
    }

 

가장 먼저 최소성에 대해 검증하였는데, 기존에 저장된 후보 키와 동일한 키를 포함하고 있는 경우에는 최소성 원칙에 어긋나게 됩니다. 기존 후보 키 자체로도 이미 유일성이 보장되는데, 굳이 거기에 더해 추가적인 키는 필요없기 때문입니다. 이때 검증 시에는 각각의 키를 저장할 Set 자료구조를 만들어 containsAll 메서드를 통해 포함 유무를 검증했습니다.

 

    private void verify(boolean[] visited) {
        StringBuilder preparatoryForeignKey = new StringBuilder();

        for (int i = 0; i < columnTotalCount; i++) {
            if (visited[i]) {
                preparatoryForeignKey.append(i);
            }
        }

        Set<Character> preparatoryForeignKeyElements = preparatoryForeignKey.chars().
            mapToObj(c -> (char) c)
            .collect(Collectors.toSet());

        for (String u : foreignKey) {
            Set<Character> foreignKeyElements = u.chars().
                mapToObj(c -> (char) c)
                .collect(Collectors.toSet());

            if (preparatoryForeignKeyElements.containsAll(foreignKeyElements)) {
                return;
            }
        }

    // ...

 

마지막으로 유일성에 대해 검증해주도록 했습니다. 별도의 Set 자료구조를 통해 릴레이션 상 특정 해당 키에 대한 튜플 데이터가 중복되는지를 검증하도록 했습니다. 최종적으로 유일성에 대해서도 검증된 경우 후보키를 저장하는 자료구조(foreignKey)에 추가해줍니다.

 

        StringBuilder columnData = new StringBuilder();

        for (int i = 0; i < rowTotalCount; i++) {
            for (int j = 0; j < columnTotalCount; j++) {
                if (visited[j]) {
                    columnData.append(relation[i][j]);
                }
            }

            String k = columnData.toString();

            if (duplicateBuffer.contains(k)) {
                return;
            }

            duplicateBuffer.add(k);
            columnData.setLength(0);
        }

        this.foreignKey.add(preparatoryForeignKey.toString());

 

전체 소스 코드

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

class Solution {

    int rowTotalCount, columnTotalCount;
    String[][] relation;
    Set<String> foreignKey = new HashSet<>();

    public int solution(String[][] relation) {
        this.relation = relation;

        rowTotalCount = relation.length;
        columnTotalCount = relation[0].length;

        boolean[] visited;

        for (int i = 1; i <= columnTotalCount; i++) {
            visited = new boolean[columnTotalCount];
            findForeignKey(0, 0, i, visited);
        }

        return foreignKey.size();
    }

    private void findForeignKey(int depth, int choiceCount, int columCount, boolean[] visited) {
        if (choiceCount == columCount) {
            verify(visited);
            return;
        }

        if (depth == columnTotalCount) {
            return;
        }

        visited[depth] = true;
        findForeignKey(depth + 1, choiceCount + 1, columCount, visited);
        visited[depth] = false;
        findForeignKey(depth + 1, choiceCount, columCount, visited);
    }

    private void verify(boolean[] visited) {
        StringBuilder preparatoryForeignKey = new StringBuilder();
        Set<String> duplicateBuffer = new HashSet<>();

        for (int i = 0; i < columnTotalCount; i++) {
            if (visited[i]) {
                preparatoryForeignKey.append(i);
            }
        }

        Set<Character> preparatoryForeignKeyElements = preparatoryForeignKey.chars().
            mapToObj(c -> (char) c)
            .collect(Collectors.toSet());

        for (String u : foreignKey) {
            Set<Character> foreignKeyElements = u.chars().
                mapToObj(c -> (char) c)
                .collect(Collectors.toSet());

            if (preparatoryForeignKeyElements.containsAll(foreignKeyElements)) {
                return;
            }
        }

        StringBuilder columnData = new StringBuilder();

        for (int i = 0; i < rowTotalCount; i++) {
            for (int j = 0; j < columnTotalCount; j++) {
                if (visited[j]) {
                    columnData.append(relation[i][j]);
                }
            }

            String k = columnData.toString();

            if (duplicateBuffer.contains(k)) {
                return;
            }

            duplicateBuffer.add(k);
            columnData.setLength(0);
        }

        this.foreignKey.add(preparatoryForeignKey.toString());
    }
}

 

참고자료

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