문제

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

---

입력

이벤트 응모자 아이디 목록이 담긴 배열 user_id와 불량 사용자 아이디 목록이 담긴 배열 banned_id가 매개변수로 주어진다.

---

출력

당첨에서 제외되어야 할 제재 아이디 목록은 몇가지 경우의 수가 가능한 지 return

---

풀이

제한조건

• user_id 배열의 크기는 1 이상 8 이하입니다.
• user_id 배열 각 원소들의 값은 길이가 1 이상 8 이하인 문자열입니다.
• 응모한 사용자 아이디들은 서로 중복되지 않습니다.
• 응모한 사용자 아이디는 알파벳 소문자와 숫자로만으로 구성되어 있습니다.
• banned_id 배열의 크기는 1 이상 user_id 배열의 크기 이하입니다.
• banned_id 배열 각 원소들의 값은 길이가 1 이상 8 이하인 문자열입니다.
• 불량 사용자 아이디는 알파벳 소문자와 숫자, 가리기 위한 문자 '*' 로만 이루어져 있습니다.
• 불량 사용자 아이디는 '*' 문자를 하나 이상 포함하고 있습니다.
• 불량 사용자 아이디 하나는 응모자 아이디 중 하나에 해당하고 같은 응모자 아이디가 중복해서 제재 아이디 목록에 들어가는 경우는 없습니다.
• 제재 아이디 목록들을 구했을 때 아이디들이 나열된 순서와 관계없이 아이디 목록의 내용이 동일하다면 같은 것으로 처리하여 하나로 세면 됩니다.

접근방법

제한조건에서 크기가 1-8이다. 따라서 완탐을 하여도 아무런 문제가 없다고 판단했다.

그리고 문제에서 가장 까다로울만한 조건순서와 관계없이 아이디 목록의 내용이 동일하다면 같은 것으로 처리을 처리하기 위해 비트마스킹을 표현하고 그 결과를 Set을 통해 관리 했다.

문제를 풀기 위해 구현해야할 항목을 중심으로 생각해보자.

특정 문자열이 제제 아이디 목록에 포함되어 있는가?
확인하기 위해서 2개의 문자열을 받아 서로 매핑 될 수 있는 문자열인지 확인한다.

// src문자열이 comp문자열에 해당하는가?
public boolean isBan(String src, String comp){
        int len1 = src.length();
        int len2 = comp.length();
        
        // 길이가 다르면 해당하지 않음.
        if(len1 != len2)
            return false;
        
        // 각 문자를 보며 일치하는지 확인.
        for(int i = 0; i < len1; ++i){
            if(src.charAt(i) == comp.charAt(i) || comp.charAt(i) == '*')
                continue;
            else
                return false;
        }
        return true;
    }

비트마스킹을 어떻게 활용할 것인가?
예제를 통해 살펴보자.

user_id	banned_id
"frodo", "fradi", "crodo", "abc123", "frodoc"	"*rodo", "*rodo", "******"

라고 한다면 나열된 순서와 관계없이 아이디 목록의 내용이 동일하다면 같은 것으로 처리하기 때문에
frodo, crodo, abc123 또는 frodo, crodo, frodoc 2개로 구할 수 있다.

비트마스킹을 생각이 먼저 떠오른 이유는 다른 방법보다 가장 단순하였기 때문이다.
frodo, crodo, abc123 과 crodo, frodo, abc123
둘 중 어느 순서로 매핑되어도 비트마스킹으로 표현하자면
01101로 표현할 수 있고, int값 만으로 Set에서 관리 할 수 있기 때문에 가장 비용이 적다고 생각했다.

아래와 같이 비트마스킹을 표현했다.

4번 id	3번 id	2번 id	1번 id	0번 id
0	1	1	0	1

-> user_id 리스트의 0,2,3번째 사람이 제재 아이디 목록에 포함되는 조합을 표현

이제 위에서 만든 함수를 순열을 이용해서 확인해보자.
흐름은 다음과 같다.

1. 제재 아이디 목록에서 하나를 고정한다.
2. 유저리스트를 순회하며 매칭되는 유저를 찾는다.
3. 매칭 되었다면 기록해두고, 제재 아이디를 다음 순서로 넘긴다.
4. 1번으로 돌아간다.

위에 적은 항목을 구현하면 아래와 같이 구현할 수 있다.

public void search(String[] user_id, String[] banned_id, int value, int depth){
        if(depth >= banned_id.length){
            resultSet.add(value);
            return;
        }
        for(int i = 0 ; i < user_id.length; ++i){
            if(visit[i]==true)
                continue;
            if(isBan(user_id[i],banned_id[depth])){
                visit[i] = true;
                int newValue = value | (1 << i);
                search(user_id, banned_id, newValue, depth + 1);
                visit[i] = false;
            }
        }
    }

---

코드

import java.util.*;

class Solution {
    Set<Integer> resultSet;
    boolean[] visit;
    
    public boolean isBan(String src, String comp){
        int len1 = src.length();
        int len2 = comp.length();
        
        if(len1 != len2)
            return false;
        
        for(int i = 0; i < len1; ++i){
            if(src.charAt(i) == comp.charAt(i) || comp.charAt(i) == '*')
                continue;
            else
                return false;
        }
        return true;
    }
    
    public void search(String[] user_id, String[] banned_id, int value, int depth){
        if(depth >= banned_id.length){
            resultSet.add(value);
            return;
        }
        for(int i = 0 ; i < user_id.length; ++i){
            if(visit[i]==true)
                continue;
            if(isBan(user_id[i],banned_id[depth])){
                visit[i] = true;
                int newValue = value | (1 << i);
                search(user_id, banned_id, newValue, depth + 1);
                visit[i] = false;
            }
        }
    }
    public int solution(String[] user_id, String[] banned_id) {
        resultSet = new HashSet();
        visit = new boolean[user_id.length];
        
        search(user_id, banned_id, 0, 0);
        
        return resultSet.size();
    }
}