[프로그래머스][JAVA] 후보키 (비트마스크)

이건 좀더 보완해본건데.. 로직 진짜 헷갈린다

Line:11~31 4중 for문 지옥이다..개헷갈림

 

바로 밑에건

"100r" "ion"

"100" "rion"나오면 틀리는 코드임

import java.util.*;
 
class Solution {
    public int solution(String[][] relation) {
        int answer = 0;
        int rowSize = relation.length;
        int colSize = relation[0].length;
 
        // candiKey 후보리스트
        List<Integer> ckCandiList = new LinkedList<>(); 
        
        Loop1:
        for(int i=1; i<(1<<colSize); i++){
            
            for(int r1=0; r1<rowSize; r1++){
                Loop2:
                for(int r2=r1+1; r2<rowSize; r2++){
                    
                    boolean isSame = true;
                    for(int j=0; j<colSize; j++){
                        if( (i&(1<<j)) == 0 ) continue;
                        if( !relation[r1][j].equals(relation[r2][j])){
                            continue Loop2;
                        }
                    }
                    if(isSame)
                        continue Loop1;
                }
            }
            
            ckCandiList.add(i);
             
        }
        
        while(!ckCandiList.isEmpty()){
            int ck = ckCandiList.remove(0);
            answer++;
            
            for(int i=0; i<ckCandiList.size(); i++){
                int ckCandi = ckCandiList.get(i);
                if( (ck&ckCandi)==ck ){
                    ckCandiList.remove(new Integer(ckCandi));
                    i--;
                }
            }
        }
        
        
        return answer;
    }
}
 

 

 

 

 

밑에 짓거리 할 필요 없이 비트마스크로 하면 된다

 

candiKey의 후보군 찾기

while문 돌려서 최소식을 깨뜨리는 canKey후보군들 지우기

 

여기서 중요한 점이

Line:37의 ckCandiList.get(0)이 항상 유일성과 최소성을 만족하는 후보키라는 사실을 알아야 한다

import java.util.*;
 
class Solution {
    public int solution(String[][] relation) {
        int answer = 0;
        int m = relation.length;
        int n = relation[0].length;
        
        //candiKey후보리스트
        List<Integer> ckCandiList = new LinkedList<>(); 
        
        Loop1:
        for(int i=1; i<(1<<n); i++){
            Map<String, Boolean> map = new HashMap<>();
            
            for(int r=0; r<m; r++){
                StringBuilder sb = new StringBuilder();
                for(int j=0; j<n; j++){
                    if( (i&(1<<j)) !=0 ){
                        sb.append(relation[r][j]);
                    }
                }
                
                String columCombStr = sb.toString();
                if(!map.containsKey(columCombStr)){
                    map.put(columCombStr,true);
                }
                else{
                    continue Loop1;
                }
            }
            
            ckCandiList.add(i);
             
        }
        
        while(!ckCandiList.isEmpty()){
            int ck = ckCandiList.remove(0);
            answer++;
            
            for(int i=0; i<ckCandiList.size(); i++){
                int ckCandi = ckCandiList.get(i);
                if( (ck&ckCandi)==ck ){
                    ckCandiList.remove(new Integer(ckCandi));
                    i--;
                }
            }
        }
        
        
        return answer;
    }
}
 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

하.. 문자열 나누기 null로나누기라고해야되나.. 

 

ex)

"abcd" ->"a" "b" "c" "d"

이렇게 나누는 방법을 몰라서 막혔음..

 

결론은 저렇게 null로 자를 수는 없고 공백을 사이에 붙이거나..

저 "abcd"를 for문으로 순회하는 수 밖에 없다.. split(str, "")하면 안쪼개지고 str원본 나온다

 

 

 

(하다가 버린 코드.... DFS할 필요 없이 속성의 조합을 비트연산자로 하면 된다..)

import java.util.*;
 
class Solution {
    private List<String> columnCombList;
    private int m, n;
    
    public int solution(String[][] relation) {
        m = relation.length;
        n = relation[0].length;
        initColumnCombList(n);
        
        
        
        
        System.out.println(columnCombList.size());
        // columnCombList.forEach(System.out::println);
        
        int answer = 0;
        for(int i=0; i<columnCombList.size(); i++){
            List<Integer> indexList = new ArrayList<>();
            
            String currComb = columnCombList.get(i);
            for(int j=0; j<currComb.length(); j++){
                indexList.add(currComb.charAt(j)-'0');
            }
            indexList.forEach(idx -> {System.out.print(idx+" ");});
            
            
            Map<String, Boolean> map = new HashMap<>();
            for(int j=0; j<m; j++){
                StringBuilder sb = new StringBuilder();
                for(int k=0; k<indexList.size(); k++){
                    sb.append(relation[j][indexList.get(k)]);
                }
                if(!map.containsKey(sb.toString())){
                    
                }else{
                    
                }   
            }
            System.out.println();
            
            
        }
        
        
        return answer;
    }
    
    private void initColumnCombList(int num){
        columnCombList = new ArrayList<>();
        
        for(int combNum=1; combNum<=num; combNum++){
            DFS(new StringBuilder(), -1, 0,combNum);
        }
        
        
    }
    
    private void DFS(StringBuilder sb, int preIdx, int depth, int combNum){
        if(depth == combNum){
            columnCombList.add(sb.toString());
            return;
        }
        for(int i=preIdx+1; i<n; i++){
            sb.append(i);
            DFS(sb, i, depth+1, combNum);
            sb.deleteCharAt(sb.length()-1);
        }
    }
}