[프로그래머스/Level2] 후보키 (JAVA)

📖 문제

프로그래머스

 

 

 

💡  풀이 방식

• DFS

 

필요 자료구조
- 속성 선택 여부 나타내는 배열 bolean[] visited = new boolean[relation[0].length]
- 후보키 목록 List<String> list 

 

 

1. 1부터 N개의 속성을 모두 선택하며 후보키가 가능한지(= 값이 중복되는 게 없는지) 확인한다. (DFS)

: 조합이 만들어지면, 유일성 검사와 최소성 검사한 후, 조합을 추가한다.

 

  1-1) 선택된 속성으로  후보키를 생성한다.

List<Integer> tmpList = new ArrayList<>();	// 임시 후보키 목록
String key = "";    // 후보키

for(int i = 0 ; i < visited.length ; i++) {
    if(visited[i]) {
        key += String.valueOf(i);
        tmpList.add(i);
    }
}

 

 

 

  1-2) 유일성 검사 메소드

Map<String, Integer> map = new HashMap<>();

for(int i = 0 ; i < relation.length ; i++) {
    String str = "";

    for(int j : tmpList) {
        str += relation[i][j];
    }

    if(map.containsKey(str))  return;	// 후보키가 중복되면 리턴
    map.put(str, 0);	// 중복되지 않으면, 목록에 추가
}

 

 

  1-3) 최소성 검사 메소드

for(String s : list) {
    int cnt = 0;

    for(int i = 0 ; i < key.length() ; i++) {
        String subS = String.valueOf(key.charAt(i));

        if(s.contains(subS)) cnt++;
    }

    if(cnt == s.length())   return;
}

 

 

 

2. 후보키 목록의 크기 = 후보키 개수를 정답으로 출력한다.

 

 

 

 

🔺 코드

import java.util.*;
 
class Solution {
    static String[][] relation;
    static boolean[] visited;   // 속성 선택 여부 나타내는 배열
    static List<String> list = new LinkedList<>();  // 후보키 목록
        
    public int solution(String[][] relation) {
        this.relation = relation;
        
        // 속성 1~N개씩 다 선택해보기
        for(int i = 1 ; i <= relation[0].length ; i++) {
            visited = new boolean[relation[0].length];
           dfs(i, 0, 0);
        }
        
        return list.size(); // 가능한 후보키 개수 리턴
    }
    
    private static void dfs(int target, int idx, int depth) {
        if(depth == target) {
            List<Integer> tmpList = new ArrayList<>();
            String key = "";    // 후보키
            
            // 선택된 속성으로 후보키 생성
            for(int i = 0 ; i < visited.length ; i++) {
                if(visited[i]) {
                    key += String.valueOf(i);
                    tmpList.add(i);
                }
            }
            
           
           // 1. 후보키 유일성 검사
           Map<String, Integer> map = new HashMap<>(); // 문자열, 출현 개수
            for(int i = 0 ; i < relation.length ; i++) {
                String str = "";
                
                for(int j : tmpList) {
                    str += relation[i][j];
                }
                
                if(map.containsKey(str))  return; // 검사하려는 키가 후보키 포함하면 유일성 만족 X
                map.put(str, 0);
            }
            
            // 2. 후보키 최소성 검사
            for(String s : list) {
                int cnt = 0;
                
                for(int i = 0 ; i < key.length() ; i++) {
                    String subS = String.valueOf(key.charAt(i));
                    
                    // 최소성 만족하는지 확인
                    if(s.contains(subS)) cnt++;
                }
                
                if(cnt == s.length())   return;
            }
            
            // 3. 1,2 모두 만족하면 후보키 추가
            list.add(key);
            
            return;
        }
        
        for(int i = idx ; i < visited.length ; i++) {
            if(!visited[i]) {
                visited[i] = true;
                dfs(target, i, depth + 1);
                visited[i] = false;
            }
        }
    }
}

 

 

 

➕ 다른 풀이 방식

 

[프로그래머스] 후보키 (JAVA/자바) - 2019 카카오 기출

 

 

- 조금 더 가독성 좋고, 이해하기 더 좋았다(?)

(Java) 프로그래머스 - 후보키

 

[프로그래머스/자바] 후보키 풀이 - 2019 KAKAO BLIND RECRUITMENT

---

💦 어려웠던 점

- DFS 문제인 건 알았는데, 유일성과 최소성 검사를 어떻게 해야할지 모르겠었다..........

 

 

🧐 새로 알게 된 내용

- 유일성과 최소성 검사하는 방법.. (사실 완벽히 이해하진 못 해서 다시 봐야함)

 

 

1회독	2회독	3회독	4회독	5회독
V

---

(참고)

[프로그래머스] 후보키(Java 자바)