[프로그래머스] 후보키

카테고리

문자열 처리

나만의 카테고리

DFS

문제 링크

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

코딩테스트 연습 - 후보키

요점

• 데이터베이스에서 후보키 특성에 대해 이해하고 있으면 편하다
• List 혹은 Array를 다루는 법에 대해 알아야한다

참고 지식

• java.util.Set

풀이 (Java)

import java.util.*;

class Solution {
    private String[][] glbRelation;
    private int relationSize;
    private int relationIndexSize;
    private int answer = 0;
    private List<Integer> indexList = new ArrayList<>();
    private List<List<Integer>> answerList = new ArrayList<>();
    
    public int solution(String[][] relation) {
        glbRelation = relation;
        relationSize = relation.length;
        relationIndexSize = relation[0].length;
        
        for (int i = 0; i < relationIndexSize; i++) {
            dfs(i);   
        }
        
        return answerList.size();
    }
    
    private void dfs(int index) {
        indexList.add(index);
        int lastIndex = indexList.size() - 1;
        
        List<Integer> tempIndexList = new ArrayList<>(indexList);
        if (isCandidateKey(tempIndexList)) {            
            removeOverlapAndAdd(tempIndexList);
            indexList.remove(lastIndex);
            return;
        }
        
        if (index == (relationIndexSize - 1)) {
            indexList.remove(lastIndex);
            return;
        }
        
        for (int i = index + 1; i < relationIndexSize; i++) {
            dfs(i);
        }
        
        if (!indexList.isEmpty()) {
            indexList.remove(lastIndex);
        }
    }
    
    private boolean isCandidateKey(List<Integer> indexList) {
        Set<String> keySet = new HashSet<>();
        
        for (String[] relation: glbRelation) {
            String temp = "";
            for (int index : indexList) {
                temp = temp + relation[index];
            }
            
            keySet.add(temp);
        }
        
        return keySet.size() == relationSize;
    }
    
    private void removeOverlapAndAdd(List<Integer> targetIndexList) {
        List<List<Integer>> nextAnswerList = new ArrayList<>();
        List<Integer> tempList = new ArrayList<>();
        
        for (int i = 0; i < answerList.size(); i++) {
            tempList = answerList.get(i);
            
            if (!(tempList.containsAll(targetIndexList))) {
                nextAnswerList.add(tempList);
            }
        }
        
        nextAnswerList.add(targetIndexList);
        answerList = nextAnswerList;
    }
}

코드는 굉장히 난잡합니다. DFS인지 BFS인지 조금 헷갈리네요. 일단은 당장 생각나는 것은 DFS여서 그대로 사용했습니다. 

 

---

알고리즘 초보가 정리한 글입니다

더 좋은 방법이나 코드에 대한 코멘트 언제나 환영합니다!