[Programmers] 후보키 (2019 카카오 블라인드)

• 성능 요약
  • 구분
• 문제풀이
• Answer Code(23.11.27)
• Reference

문제 링크

성능 요약

• 메모리: 70.4 MB, 시간: 3.66 ms

구분

• 코딩테스트 연습 > 2019 KAKAO BLIND RECRUITMENT

문제풀이

먼저, 주어진 데이터베이스의 릴레이션에서 후보키의 개수를 찾는 문제입니다.

주어진 String 타입의 2차원 배열 relation에서 후보키의 개수를 찾아 반환합니다.

코드는 재귀적인 방식인 깊이 우선 탐색(DFS)을 사용하여 후보키를 찾습니다.

먼저, 주어진 데이터베이스의 릴레이션에서 후보키의 개수를 찾는 문제입니다. 주어진 String 타입의 2차원 배열 relation 에서 후보키의 개수를 찾아 반환합니다. 코드는 재귀적인 방식인 깊이 우선 탐색(DFS)을 사용하여 후보키를 찾습니다.

1. 전역 변수 및 메서드:
   • List<String> candi: 후보키를 저장하는 리스트입니다.
   • dfs 메서드: 깊이 우선 탐색을 수행하는 메서드로, 후보키를 찾기 위해 가능한 모든 조합을 탐색합니다.

이 부분은 dfs 메서드로, 깊이 우선 탐색(Depth-First Search)을 수행하여 후보키를 찾아내는 역할을 합니다. 코드를 한 부분씩 살펴보겠습니다.

1. 깊이가 목표 깊이에 도달했을 때:

    if (depth == end) {
        // ...
    }
       
   

   • depth가 end와 같아지면, 즉, 조합이 완성된 경우입니다.
   • 조합을 확인하고 유일성을 검사하는 부분입니다.

2. 조합 확인 및 유일성 검사:

    List<Integer> list = new ArrayList<>();
    String key = "";
    for (int i = 0; i < visited.length; i++) {
        if (visited[i]) {
            key += String.valueOf(i);
            list.add(i);
        }
    }
       
   

   • 선택된 열의 인덱스를 list에 저장하고, key에는 해당 인덱스를 문자열로 연결합니다.

3. 중복 체크를 위한 Map 생성 및 유일성 검사:

    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);
        }
    }
       
   

   • 조합을 이용하여 만들어진 문자열 s를 이용해 map에 저장하여 유일성을 체크합니다.
   • 이미 존재하는 경우(map.containsKey(s)), 중복된 튜플이므로 함수를 종료합니다.

4. 최소성 검사 및 후보키 추가:

    for (String s : candi) {
        int count = 0;
        for(int i = 0; i < key.length(); i++){
            String subS = String.valueOf(key.charAt(i));
            if(s.contains(subS)) count++;
        }
        if (count == s.length()) return;
    }
       
   

   • 현재 후보키(key)가 이미 저장된 후보키들 중에서 어떤 것에도 속하지 않는지를 확인합니다.
   • count를 통해 일치하는 문자열의 개수를 셉니다.
   • 만약 count가 현재 후보키의 길이와 같다면, 현재 후보키는 이미 저장된 후보키의 일부이므로 함수를 종료합니다.
   • 그렇지 않으면, candi 리스트에 후보키를 추가합니다.

5. 재귀 호출을 통한 깊이 우선 탐색:

    for (int i = start; i < visited.length; i++) {
        if (visited[i]) continue;
       
        visited[i] = true;
        dfs(visited, i, depth + 1, end, relation);
        visited[i] = false;
    }
       
   

   • 재귀 호출을 통해 깊이 우선 탐색을 수행합니다.
   • 현재 선택한 열을 방문 표시하고, 깊이를 증가시켜 재귀 호출을 합니다.
   • 재귀 호출이 끝나면 방문 표시를 해제하여 이전 상태로 돌아갑니다.

이렇게 하면 dfs 메서드는 주어진 릴레이션에서 모든 가능한 후보키를 찾아내는 역할을 합니다.

Answer Code(23.11.27)

import java.util.*;

class Solution {
    List<String> candi = new ArrayList<>();

    public int solution(String[][] relation) {
        int answer = 0;

        for (int i = 0; i < relation[0].length; i++) {
            boolean[] visited = new boolean[relation[0].length];
            dfs(visited, 0, 0, i + 1, relation);
        }
        answer = candi.size();
        return answer;
    }

    public void dfs(boolean[] visited, int start, int depth, int end, String[][] relation) {
        if (depth == end) {
            List<Integer> list = new ArrayList<>();
            String key = "";
            for (int i = 0; i < visited.length; i++) {
                if (visited[i]) {
                    key += String.valueOf(i);
                    list.add(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);
                }
            }

            // 후보키 추가
            for (String s : candi) {
                int count = 0;
                for(int i = 0; i < key.length(); i++){
                    String subS = String.valueOf(key.charAt(i));
                    if(s.contains(subS)) count++;
                }
                if (count == s.length()) return;
            }
            candi.add(key);

            return;
        }

        for (int i = start; i < visited.length; i++) {
            if (visited[i]) continue;

            visited[i] = true;
            dfs(visited, i, depth + 1, end, relation);
            visited[i] = false;
        }

    }
}

Reference

• https://tmdrl5779.tistory.com/219)