후보키 [프로그래머스]

1) 문제 접근 방법

(1) DFS를 통해, 순회하면서, relation의 col의 개수에 해당하는 범위(0이상 col-1 이하)에서 col의 위치를 선택합니다.

    -> 그리고 그 값들을 picked라는 ArrayList에 저장합니다. 

    -> 이 때, 순차적으로만 picked에 선언하기 위해서 lastPick이라는 변수를 활용합니다. 

(2) picked에 1개 이상의 값이 저장되면, 선택된 col들을 통해서 

     유니크한 row를 식별해낼 수 있는지 판단한다.

-> 이를 위해 checkUnique라는 메소드를 선언합니다. 

(2-1) checkUnique 메소드는 picked를 기준으로, 해당 picked에 속하는 col들에 있는 값들을 

         String으로 묶어서 만든 다음에, set에 저장합니다.

(2-2) 만약에 set이 row의 개수와 같다면, 해당 picked의 col들로 unique하게 식별된 것이므로,

         true를 반환합니다.

(2-3) checkUnique 메소드가 true를 반환하면, picked에 포함된 col 값들로 String을 만들어주고,

         해당 str을 uniqueArr이라는 ArrayList에 저장합니다. 

(3) picked의 size가 만약 col과 같아졌다면, return을 해줍니다.

 

(4) 다음은 uniqueArr ArrayList에 담긴 값들로, minimial한지를 판단합니다. 

-> minimal 한지 판단하기 전에, 우선 uniqueArr에 담긴 값들을 길이에 따라 정렬해줍니다.

-> 길이가 작은 것이 앞에 오도록 정렬해줍니다. 

-> 이것을 하는 이유는, 

   (4-1) 우선은 길이가 1인 것은 항상 minimal하므로, minimal하다고 판단해줍니다.

            그리고 minimals ArrayList에 저장합니다. 

           -> 이렇게 minimals ArrayList를 확실히 분리함으로써, 명확한 기준점을 제공합니다. 

   (4-2) 길이가 2이상인 것은 minimals ArrayList에 들어있는 값과 비교해서 

            minimal한지 판단해줍니다. 

          -> minimal한지 판단할 때는, 판단하고자 하는 String이 minimal의 값들을 모두 갖고 있으면,

              minimal하지 않다고 판단합니다 .

   (4-3) minimal하다고 판단되는 경우에만, minimals ArrayList에 추가합니다. 

 

- 회고

(1) 처음에 minimal을 구하는 과정에서 테스트 케이스가 틀리는 현상이 발생했다

-> 그 이유는, 우선

  (1-1) minimal을 구하는 기준을 명확히 세우지 않은 점

  -> minimal을 구하는 기준은 길이가 작은 것부터 긴 순으로 해야 한다.  

  -> 즉, minimals라는 ArrayList를 독립적으로 활용하고,

  -> 1차원 for문으로 순회하면서, 해당 케이스가 minimal한지만 판단하는 것에 집중하는 것이 좋다.

 -> 2차원 for문을 활용하니 혼동이 왔다. 

  (1-2) minimal에 대한 처리를 잘못한 점

  -> 예를 들어, 13 과 23은 서로 하나가 다른 하나로 인해 minimal이 되지 않는 관계가 아니다. 

  이 영향을 미쳤다

-> minimal 처리를 어떻게 더 잘할 수 있을지 찾아보고, 적용해봐야겠다. 

 

import java.util.*; 

class Solution {
    
    public static int row; 
    public static int col; 
    public static ArrayList<String> uniqueArr; 
    
    
    public static boolean checkMinimal(String target, ArrayList<String> minimals){
        
        
        for(int i=0; i<minimals.size(); i++){
            String minimal = minimals.get(i);
            int cnt = 0; 
            
            for(int j=0; j<minimal.length(); j++){
                char c = minimal.charAt(j);
                if(target.contains(Character.toString(c))){
                    cnt++;
                }
            }
            
            if(cnt == minimal.length()){
                return false;
            }
            
        }
        
        return true; 
        
        
    }
    
    public static boolean checkUnique(String[][] relation, ArrayList<Integer> picked){
        
        HashSet<String> set = new HashSet<>(); 
        boolean[] pick = new boolean[col];
        
        for(int i=0; i<picked.size(); i++){
            int num = picked.get(i);
            pick[num] = true;
        }
        
        for(int i=0; i<row; i++){
            String tmp = "";
            
            for(int j=0; j<col; j++){
                if(pick[j] == true){
                    tmp += relation[i][j];
                }
            }
            
            set.add(tmp);
        }
        
        if(set.size() == row){
            return true;
        }else{
            return false; 
        }
        
    }
    
    public static void dfs(String[][] relation, ArrayList<Integer> picked){
        
        if(picked.size() >= 1){
            
            boolean res = checkUnique(relation, picked);
            
            if(res){
                String str = "";
                
                for(int i=0; i<picked.size(); i++){
                    str += Integer.toString(picked.get(i));
                }
                
                uniqueArr.add(str);
            }
            
        }
        
        if(picked.size() == col){
            return; 
        }
        
        int lastPick = 0; 
        if(picked.size() == 0){
            lastPick = 0;
        }else{
            lastPick = picked.get(picked.size()-1)+1;
        }
        
        for(int i=lastPick; i<col; i++){
            picked.add(i);
            dfs(relation, picked);
            picked.remove(picked.size()-1);
        }
        
        
    }
    
    
    public int solution(String[][] relation) {
        int answer = 0;
        
        row = relation.length; 
        col = relation[0].length; 
        
        ArrayList<Integer> picked = new ArrayList<>();
        uniqueArr = new ArrayList<>(); 
        
        dfs(relation, picked);
        
        ArrayList<String> minimals = new ArrayList<>();
        
        Collections.sort(uniqueArr, (o1, o2) -> Integer.compare(o1.length(), o2.length()));
        
        for(int i=0; i<uniqueArr.size(); i++){
            String str = uniqueArr.get(i);
            if(str.length() == 1){
                minimals.add(str);
            }else{
                boolean res = checkMinimal(str, minimals);
                // System.out.println("str, res는?" + str + " " + res);
                if(res){
                    minimals.add(str);
                }
            }
        }
        
        
        return minimals.size();
    }
}