[Java] 프로그래머스 - 후보키 (2단계)

코딩 테스트 풀이 체크리스트
2시간 내에 풀었는가?	X
본인의 실력으로 풀었는가?	O

 

코딩테스트 연습 - 후보키

 

 

 

 

 

import java.util.*;
class Solution {
    int col, row;
    ArrayList<String> arr;
    ArrayList<String[]> answer;
    public int solution(String[][] relation) {
        answer = new ArrayList<>();
        col = relation[0].length;
        row = relation.length;
        arr = new ArrayList<>();
        
        //후보키 조합 만들기
        create(0, "");
        
        //길이 기준으로 오름차순 정렬
        Collections.sort(arr, new Comparator<String>(){
            @Override
            public int compare(String a, String b) {
                return a.length() - b.length();
            }
        });
        
        //최소성 확인하고 유일성 확인
        for (int i = 0; i < arr.size(); i++) {
            String[] s = arr.get(i).split("");
            if (check(s)) make(relation, s);
        }
        
        return answer.size();
    }
    
    //유일성 확인 함수
    public void make(String[][] r, String[] s) {
        HashMap<String, Integer> m = new HashMap<>();
        
        //글자를 만들면서 중복이 있는지 없는지 파악
        for (int i = 0; i < row; i++) {
            StringBuilder sb = new StringBuilder();
            for (int j = 0; j < s.length; j++) {
                sb.append(r[i][Integer.parseInt(s[j])]);
            }
            
            String str = sb.toString();
            if (m.getOrDefault(str, 0) != 0) return;
            
            m.put(str, 1);
        }
        
        answer.add(s);
    } 
    
    //최소성 확인 함수
    public boolean check(String[] s) {
        List<String> list = Arrays.asList(s);
        
        //answer이랑 비교하면서 answer에 있는 조합이 s에 들어 있는지를 파악함
        for (int i = 0; i < answer.size(); i++) {
            String[] a = answer.get(i);
            if (a.length > s.length) continue;
            boolean value = false;
            for (int m = 0; m < a.length; m++) {
                if (list.indexOf(a[m]) == -1) {
                    value = true;
                    break;
                }
            }
            
            if (!value) return false;
        }
        
        return true;
    }
    
    public void create(int num, String s) {
        for (int i = num; i < col; i++) {
            StringBuilder temp = new StringBuilder(s);
            temp.append(i);
            String str = temp.toString();
            arr.add(str);
            create(i + 1, str);
        }
    }
}

 

테스트 1 〉	통과 (1.35ms, 76.1MB)
테스트 2 〉	통과 (1.81ms, 80.9MB)
테스트 3 〉	통과 (2.85ms, 75.7MB)
테스트 4 〉	통과 (1.31ms, 65.6MB)
테스트 5 〉	통과 (1.23ms, 70.6MB)
테스트 6 〉	통과 (0.64ms, 77.9MB)
테스트 7 〉	통과 (0.61ms, 72.7MB)
테스트 8 〉	통과 (0.52ms, 76MB)
테스트 9 〉	통과 (1.26ms, 76.9MB)
테스트 10 〉	통과 (1.53ms, 76.3MB)
테스트 11 〉	통과 (1.93ms, 71MB)
테스트 12 〉	통과 (6.75ms, 73.3MB)
테스트 13 〉	통과 (2.38ms, 73.6MB)
테스트 14 〉	통과 (1.04ms, 76.2MB)
테스트 15 〉	통과 (1.06ms, 75.5MB)
테스트 16 〉	통과 (0.88ms, 75.5MB)
테스트 17 〉	통과 (1.10ms, 77.4MB)
테스트 18 〉	통과 (5.92ms, 76.1MB)
테스트 19 〉	통과 (8.20ms, 75.7MB)
테스트 20 〉	통과 (10.14ms, 82.7MB)
테스트 21 〉	통과 (8.65ms, 76.9MB)
테스트 22 〉	통과 (7.08ms, 77.7MB)
테스트 23 〉	통과 (1.38ms, 79.6MB)
테스트 24 〉	통과 (7.81ms, 80MB)
테스트 25 〉	통과 (9.30ms, 69.9MB)
테스트 26 〉	통과 (8.15ms, 77.5MB)
테스트 27 〉	통과 (2.61ms, 73.2MB)
테스트 28 〉	통과 (4.45ms, 76.2MB)