프로그래머스 lv2 - 후보키 (자바) [2019 KAKAO BLIND RECRUITMENT]

문제

---

프로그래머스 lv2 - 후보키

풀이

---

• 백트래킹을 통해 전체 후보키 조합을 만듬
  ex) column이 4개인 경우 1,2,3,4,12,13,14,23,24,34,123,124...
• 만든 후보키마다 후보키가 될 수 있는지 체크
  • 유일성 체크
    • map 자료구조를 사용하여 중복된 후보키가 존재하는지 체크
  • 최소성 체크
    • 이미 14인 후보키가 있을 때 134 키가 후보키가 되는지 체크하려면 234중 14가 있으면 안됨

어려웠던 점

---

• 백트래킹까지는 구현했지만, 후보키의 중복 처리를 위해 유일성을 체크할 때 column 값들을 전부 string으로 합쳐서 만들 생각 하지 못함
• 현재 후보키를 백트래킹을 통해 찾은 인덱스들을 문자열로 바꿔서 합친 형태로 후보키로 만들어 처리할 생각 하지 못함
  -> 백트래킹을 통해 찾은 후보키 조합 인덱스가 1,3인 경우 -> String "13"으로 바꿔서 해당 문자열을 후보키 판단 여부에 사용

코드

---

import java.util.*;
class Solution {
    ArrayList<String> candi = new ArrayList<>();
    public int solution(String[][] relation) {
        ArrayList<Integer> list = new ArrayList<>();
        dfs(0, list, relation);

        int answer = candi.size();

        return answer;
    }

    void dfs(int idx, ArrayList<Integer> list, String[][] relation) {
        check(list, relation);
        if (idx == relation[0].length)
            return;

        for (int i = idx; i < relation[0].length; i++) {
            list.add(i);
            dfs(i + 1, list, relation);
            list.remove(list.size() - 1);
        }
    }

    void check(ArrayList<Integer> list, String[][] relation) {
        String key = "";
        for (int i : list)
            key += String.valueOf(i);

        Map<String, Integer> map = new HashMap<>(); // 중복되는 행이 있는지 체크
        for (int i = 0; i < relation.length; i++) {
            String s = "";
            for (Integer j : list)
                s += relation[i][j];

            if (map.containsKey(s))
                return;
            else
                map.put(s, 0);
        }

        // 후보키 추가 - ex) 13이 후보키로 있고 새로운 키가 134인 경우 13이 포함되면 후보키 X
        for (String s : candi) {
            int count = 0;
            for (int i = 0; i < key.length(); i++) {
                String sub = String.valueOf(key.charAt(i));
                if (s.contains(sub)) count++;
            }
            if (count == s.length()) return;
        }

        candi.add(key);
        return;
    }
}

참고

---

유일성, 최소성 체크를 구글링의 도움을 받았다