프로그래머스(후보키)-문자열, 조합

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

프로그래머스

1. 걸린 시간

1시간 30분

2. 트리거

후보키 조합을 모두 뽑고, 최소성과 유일성을 검사한다.

이때, 최소성 평가에서 주의할 점이 있다.

 

03이라는 후보키가 있을 때, 0123을 검사하기 위해서 String의 contains를 쓰면, 0123에서 0과 3이 붙어있지 않기 때문에, +1이되게 된다.

즉, 0과 3으로 나눈 뒤, 0,1,2,3에 0,3 둘다 포함하는지 확인하는 로직을 구현해야 한다.

import java.util.*;

class Solution {
    static int columnSize;
    static Set<String>[] combinations;
    public int solution(String[][] relation) {
        initialize(relation);
        int answer = solve(relation);
        return answer;
    }
    
    private int solve(String[][] relation) {
        for(int i = 1; i <= columnSize; i++) {
            recursive(0, 0, i, new StringBuilder());
        }
        
        int answer = 0;
        Set<String> uniqueKey = new HashSet<>();
        for(int i = 1; i <= columnSize; i++) {
            for(String key : combinations[i]) {
                if(isOk(key, uniqueKey, relation)) {
                    answer++;
                }
            }
        }
        return answer;
    }
    
    private boolean isOk(String key, Set<String> uniqueKey, String[][] relation) {
        for (String k : uniqueKey) {
            int cnt = 0;
            for (int i = 0; i < k.length(); i++) {
                char col = k.charAt(i);
                for (int j = 0; j < key.length(); j++) {
                    if (key.charAt(j) == col) {
                        cnt++;
                        break;
                    }
                }
            }
        if (cnt == k.length()) return false;
    }
        int keySize = key.length();
        int rowSize = relation.length;
        Set<String> values = new HashSet<>();
        for(int i = 0; i < rowSize; i++) {
            StringBuilder stb = new StringBuilder();
            for(int j = 0; j < key.length(); j++) {
                stb.append(relation[i][key.charAt(j) - '0']);
            }
            if(values.contains(stb.toString())) {
                return false;
            }
            values.add(stb.toString());
        }
        
        uniqueKey.add(key);
        return true;
    }
    
    private void recursive(int currIndex, int currSize, int size, StringBuilder stb) {
        if(size == currSize) {
            combinations[size].add(stb.toString());
            return;
        }
        
        for(int i = currIndex; i < columnSize; i++) {
            stb.append(i);
            recursive(i + 1, currSize + 1, size, stb);
            stb.deleteCharAt(stb.length()-1);
        }
    }
    
    private void initialize(String[][] relation) {
        columnSize = relation[0].length;
        combinations = new Set[columnSize + 1];
        for(int i = 1; i <= columnSize; i++) {
            combinations[i] = new HashSet<>();
        }
    }
}