[틀림] [Java] 프로그래머스 불량사용자 // 순열조합, set, 비트마스킹

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

프로그래머스

* 시도1

nCm개를 뽑은후, 앞에서부터 하나씩보면서 짝이있는지 bit에저장하고,

bit가 전부 켜져있는지 보면 될듯?

반례) 예시3의 경우, frodo가 첫번째 와일드카드로 간다면, fradi는 갈곳이 없어서 오답이 되버린다.

빨간경로로 간다면, 가능해진다.

즉, 앞에서부터 하나씩 탐색하면 안되고, 모든 경우의수 순열을 완탐해야한다.

 

* 풀이

1. nPn을 순열돌린다. [ 0 1 2 3 ] [ 0 1 3 2] ...

2. 앞에서 m개만본후, 대체될수있으면, tmp에 push한다.

3. size가 같으면, 가능한 조합

4. tmp 정렬

5. set에 넣기

6. answer= set.size();

정답코드

import java.util.*;
class Solution {
    static int answer;
    static int n,m;
    static String[] uid,bid;
    static boolean[] vis = new boolean[9];
    static Set<String> resultSet = new HashSet<>(); // 중복 제거를 위한 Set 추가
    
    //a와 b가 매칭되는지
    static boolean go2(String a, String b){
        if(a.length()!=b.length()) return false;
        
        for(int i=0;i<a.length();++i){
            if(b.charAt(i)=='*'){
                continue;
            }
            if(a.charAt(i)!=b.charAt(i)){
                return false;
            }
        }
        return true;
    }
    
    static void perm(ArrayList<Integer> v, boolean[] visited) {
        // 기저 조건: m개를 모두 뽑았으면 결과 사용
        if (v.size() == n) {
            // 예: 결과 출력 또는 go(v) 호출
            // System.out.println(v);
            dfs(v);
            return;
        }

        // 0부터 n-1까지 모든 후보 인덱스 시도
        for (int i = 0; i < n; ++i) {
            if (!visited[i]) {             // 아직 사용되지 않은 인덱스만
                visited[i] = true;         // i 선택
                v.add(i);

                perm(v, visited);       // 다음 자리 재귀

                v.remove(v.size() - 1);    // 백트래킹
                visited[i] = false;        // i 선택 해제
            }
        }
    }
    
    //v : nPn 순열 인덱스
    static void dfs(ArrayList<Integer> v){
        ArrayList<String> tmp = new ArrayList<>();
        for(int i=0;i<m;++i){
            String u = uid[v.get(i)];
            if(go2(u,bid[i])){
                tmp.add(u);
            }
        }
        
        StringBuilder sb = new StringBuilder();
        if(tmp.size()==bid.length){
            Collections.sort(tmp);
            for(String s : tmp){
                sb.append(s);
            }
            resultSet.add(sb.toString());
        }
    }
    
    static void combi(int idx, ArrayList<Integer> v){
        if(v.size()==m){
            // for(int i : v){
            //     System.out.print(i+" ");
            // }
            // System.out.println();
            dfs(v);
            return;
        }
        
        for(int i=idx+1;i<n;++i){
            v.add(i);
            combi(i,v);
            v.remove(v.size()-1);
        }
    }
    
    public int solution(String[] user_id, String[] banned_id) {
        n=user_id.length;
        m=banned_id.length;
        uid=user_id;
        bid=banned_id;
        
        // ArrayList<Integer> v = new ArrayList<>();
        // combi(-1,v);
        
        perm(new ArrayList<Integer>(), new boolean[9]);
        answer=resultSet.size();
        return answer;
    }
}

 

비트마스킹 풀이

순열, 조합의 경우 비트마스킹으로 풀면 간결해진다.

n이 8로 작기때문에 비트마스킹을 할 수 있다.

bid에서 uid로 간선을 연결해야되는 그림을 생각해보자.

 

import java.util.*;
class Solution {
    static int answer;
    static int n,m;
    static String[] uid,bid;
    static Set<Integer> resultSet = new HashSet<>(); // 중복 제거를 위한 Set 추가
    
    //a와 b가 매칭되는지
    static boolean check(String a, String b){
        if(a.length()!=b.length()) return false;
        
        for(int i=0;i<a.length();++i){
            if(b.charAt(i)=='*'){
                continue;
            }
            if(a.charAt(i)!=b.charAt(i)){
                return false;
            }
        }
        return true;
    }
    
    void dfs(int i, int bit){
        if(i==m){
            resultSet.add(bit);
            return;
        }
        
        for(int j=0;j<n;++j){
            if((bit & (1<<j)) > 0) continue; //이미 방문한 곳
            if(!check(uid[j],bid[i])) continue; //갈수 없는 곳
            dfs(i+1, bit | (1<<j));
        }
    }
    

    
    public int solution(String[] user_id, String[] banned_id) {
        n=user_id.length;
        m=banned_id.length;
        uid=user_id;
        bid=banned_id;
        
        dfs(0,0);
        answer=resultSet.size();
        return answer;
    }
}

 

자바 조합, 순열 코드

조합

static void combi(int idx, ArrayList<Integer> v){
        if(v.size()==m){
            // for(int i : v){
            //     System.out.print(i+" ");
            // }
            // System.out.println();
            dfs(v);
            return;
        }
        
        for(int i=idx+1;i<n;++i){
            v.add(i);
            combi(i,v);
            v.remove(v.size()-1);
        }
    }
    
    perm(new ArrayList<Integer>(), new boolean[9]);

순열

combi에서 visited를 추가해주고, i=0~n까지 돌리면된다. idx가 필요없다.

static void perm(ArrayList<Integer> v, boolean[] visited) {
        // 기저 조건: m개를 모두 뽑았으면 결과 사용
        if (v.size() == n) {
            // 예: 결과 출력 또는 go(v) 호출
            // System.out.println(v);
            dfs(v);
            return;
        }

        // 0부터 n-1까지 모든 후보 인덱스 시도
        for (int i = 0; i < n; ++i) {
            if (!visited[i]) {             // 아직 사용되지 않은 인덱스만
                visited[i] = true;         // i 선택
                v.add(i);

                perm(v, visited);       // 다음 자리 재귀

                v.remove(v.size() - 1);    // 백트래킹
                visited[i] = false;        // i 선택 해제
            }
        }
    }
    
    ArrayList<Integer> v = new ArrayList<>();
    combi(-1,v);

 

자바 length vs size()

length는 String의 필드이다. String a, a.length (O)

size()는 컬렉션의 함수이다.ArrayList<Integer> v , v.size() (O)