프로그래머스 - 불량 사용자

코딩테스트 연습 - 불량 사용자

밴 아이디에 매칭되는 유저 아이디 찾기

---

밴 아이디의 조합의 개수를 묻는 문제이기 때문에, 우선 각 밴 아이디가 매칭되는 문자열들을 찾아야 한다. 응모자 아이디와 밴 아이디가 다음과 같다고 할 때, 

유저 아이디	밴 문자열
frodo	fr*d*
fradi	abc1**
crodo
abc123
frodoc

"fr*d*" 라는 밴 문자열은 "frodo","fradi" 라는 두 개의 유저 아이디와 매칭된다. 또 abc1** 은 abc123 이라는 단 한 개의 문자열과 매칭된다. 이런식으로 각 밴 아이디 별로 매칭되는 유저 아이디의 인덱스를 리스트 형태로 저장한다. 그러면 위 예는 다음과 같은 리스트들이 나온다. 

밴 아이디에 매칭되는 유저 아이디 판별

우선 밴 아이디와 유저 아이디가 매칭되려면 둘의 길이가 똑같아야 한다. 만약 길이가 다르면 매칭되지 않는다. 길이가 같다면, *가 아닌 인덱스의 문자를 서로 비교한다. 만약 *를 제외한 모든 문자가 같다면 둘은 매칭된다.

private boolean match(String user_id, String banned_id) {
        if (user_id.length() == banned_id.length()) {
            for (int i = 0; i < user_id.length(); i++) {
                //*를 제외한 문자가 동일하지 않으면 매칭 X
                if (banned_id.charAt(i) != '*' && banned_id.charAt(i) != user_id.charAt(i)) {
                    return false;
                }
            }
            //문자열 검사가 정상적으로 완료되면 매칭 O
            return true;
        }
        //유저 아이디와 밴 아이디의 길이가 다르면 매칭 X
        else {
            return false;
        }
    }

밴 아이디 별로 매칭 리스트 만들기

위 검사 함수를 활용해서 각 밴 아이디별로 대응되는 유저 아이디의 인덱스를 인리스트에 저장한다. 

public void getMatchedId(String[] user_id, String[] banned_id) {
    for (int i = 0; i < banned_id.length; i++) {
        for (int j = 0; j < user_id.length; j++) {
            //만약 유저 아이디와 밴 아이디가 일치하면 리스트에 저장
            if (match(user_id[j], banned_id[i])) {
                list[i].add(j);
            }
        }
    }
}

각 밴 아이디에 대응하는 유저 아이디를 골라서 조합을 만들기

---

각 밴 아이디로 대응하는 유저 아이디의 리스트를 구했으면, 이제 각 밴 아이디에 대응하는 유저 아이디를 한 개씩 선택해서 조합을 만들면 된다. 이 때 다른 밴 아이디가 고른 유저 아이디는 선택하면 안 되므로, boolean 배열을 사용해 유저 아이디의 사용여부를 검사한다. 

 

브루트 포스의 형식으로 모든 경우를 다 계산해보면 되는데, 이 때 중요한 것은 다른 밴 아이디가 고른 유저 아이디를 고르면 안되고, 또 이미 나온 조합을 다시 고르는 경우는 카운트로 세면 안 된다는 것이다. 따라서 밴 아이디가 유저 아이디의 인덱스를 선택할 때마다 비트 연산을 통해 유저 아이디 인덱스의 비트를 1로 바꿔주자. 모든 밴 아이디가 대응하는 문자열을 선택했을 때 해당 조합은 하나의 정수로 표현 가능하다. 

 

예를 들어 위의 경우에서 fradi,abc111 의 케이스를 만들었다고 생각해보자. fradi의 인덱스는 0이고 abc111의 인덱스는 3 이므로 비트 연산을 통해 만들어진 방문 판별 정수는 2진수로 1001 이 된다. 이것을 해쉬맵으로 관리하면, 이미 나온 케이스인지 쉽게 판별할 수 있다.

public int brute_force(int end, int count, boolean[] use, int visit) {
        //만약 모든 밴 아이디에 대응하는 유저 아이디를 선택했으면
        if (end == count) {
            //만약 조합이 이미 나온 적 없으면
            if (!visited.containsKey(visit)) {
                visited.put(visit, true);
                return 1;
            }
            //조합이 이미 나온적 있다면 0 반환
            else {
                return 0;
            }
        }
        int ret = 0;

        for (int i = 0; i < list[count].size(); i++) {
            //다른 밴 아이디가 해당 유저 아이디를 사용하지 않으면
            if (!use[list[count].get(i)]) {
                use[list[count].get(i)] = true;
                //이번 유저 인덱스를 사용했으므로 bit 연산을 통해 visit 정수 갱신
                ret += brute_force(end, count + 1, use, visit | (1 << list[count].get(i)));
                use[list[count].get(i)] = false;
            }
        }

        return ret;
    }

전체 코드

---

package per.jongho;

import java.io.IOException;
import java.util.ArrayList;
import java.util.HashMap;

public class BadUser {
    ArrayList<Integer>[] list;
    HashMap<Integer, Boolean> visited = new HashMap<>();

    public static void main(String[] args) throws IOException {
        BadUser badUser = new BadUser();
        String[] user_id = {"frodo", "fradi", "crodo", "abc123", "frodoc"};
        String[] banned_id = {"fr*d*", "*rodo", "******", "******"};
        System.out.println(badUser.solution(user_id, banned_id));
    }

    public int solution(String[] user_id, String[] banned_id) {
        list = new ArrayList[banned_id.length];
        for (int i = 0; i < banned_id.length; i++) {
            list[i] = new ArrayList<>();
        }
        getMatchedId(user_id, banned_id);
        return brute_force(banned_id.length, 0, new boolean[user_id.length], 0);
    }

    public int brute_force(int end, int count, boolean[] use, int visit) {
        //만약 모든 밴 아이디에 대응하는 유저 아이디를 선택했으면
        if (end == count) {
            //만약 조합이 이미 나온 적 없으면
            if (!visited.containsKey(visit)) {
                visited.put(visit, true);
                return 1;
            }
            //조합이 이미 나온적 있다면 0 반환
            else {
                return 0;
            }
        }
        int ret = 0;

        for (int i = 0; i < list[count].size(); i++) {
            //다른 밴 아이디가 해당 유저 아이디를 사용하지 않으면
            if (!use[list[count].get(i)]) {
                use[list[count].get(i)] = true;
                //이번 유저 인덱스를 사용했으므로 bit 연산을 통해 visit 정수 갱신
                ret += brute_force(end, count + 1, use, visit | (1 << list[count].get(i)));
                use[list[count].get(i)] = false;
            }
        }

        return ret;
    }

    public void getMatchedId(String[] user_id, String[] banned_id) {
        for (int i = 0; i < banned_id.length; i++) {
            for (int j = 0; j < user_id.length; j++) {
                //만약 유저 아이디와 밴 아이디가 일치하면 리스트에 저장
                if (match(user_id[j], banned_id[i])) {
                    list[i].add(j);
                }
            }
        }
    }

    private boolean match(String user_id, String banned_id) {
        if (user_id.length() == banned_id.length()) {
            for (int i = 0; i < user_id.length(); i++) {
                //*를 제외한 문자가 동일하지 않으면 매칭 X
                if (banned_id.charAt(i) != '*' && banned_id.charAt(i) != user_id.charAt(i)) {
                    return false;
                }
            }
            //문자열 검사가 정상적으로 완료되면 매칭 O
            return true;
        }
        //유저 아이디와 밴 아이디의 길이가 다르면 매칭 X
        else {
            return false;
        }
    }
}