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

[문제]

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

프로그래머스

[풀이]

우선 banned_id[]를 탐색하며 각 banned_id에 대응될 수 있는 user_id들의 index값을 bandList.get(index)에 저장하였습니다. 이때, ban이 가능한 이름인지 boolean banned(String ban, String name)을 통해 *가 아닌 문자들을 비교하며 확인합니다. 입출력 예1을 예시로 살펴보면, 아래와 같이 banList가 초기화 됩니다.

[[0, 1], [3]]

 

 

다음으로 void makeSet(String[] user_id, String[] banned_id, int cnt, String set, boolean[] visit)을 호출하여 가능한 조합들을 뽑아서 매핑이 완료된 user_id의 조합을 각 index가 오름차순으로 정렬하여 String 형태로 저장한 값을 names에 추가합니다. 이때 names를 사용하는 이유는 순서가 다르더라도, 같은 이름들이 저장된 경우 중복으로 처리해야하기 때문입니다.

(index들을 오름차순으로 정렬하기 위해 Arrays.sort()를 활용하였습니다.)

 

매핑이 모두 완료된 예시1의 names는 아래와 같습니다.

[03, 13]

마지막으로 names의 크기를 구해 answer에 저장한 후 반환합니다.

 

[코드]

import java.util.*;
class Solution {
    public static ArrayList<String> names = new ArrayList<String>();
    public static ArrayList<ArrayList<Integer>> banList = new ArrayList<ArrayList<Integer>>();
    public static int N;
    public int solution(String[] user_id, String[] banned_id) {
        int answer = 0;
        N = banned_id.length;
        for(int i=0;i<N;i++) {
            banList.add(new ArrayList<Integer>());
            for(int j=0;j<user_id.length;j++) {
                if(banned(banned_id[i], user_id[j])) {
                    banList.get(i).add(j);
                }
            }
        }
        boolean[] visit = new boolean[user_id.length];
        makeSet(user_id, banned_id, 0, "", visit);
        answer = names.size();
        return answer;
    }
    public static void makeSet(String[] user_id, String[] banned_id, int cnt, String set, boolean[] visit) {
        if(cnt == N) {
            char[] StringtoChar = set.toCharArray();
            Arrays.sort(StringtoChar);
            String str = new String(StringtoChar);
            if(!names.contains(str)) {
                names.add(str);
            }
            return;
        }
        for(Integer i:banList.get(cnt)) {
            if(visit[i]) {
                continue;
            }
            visit[i] = true;
            String nextStr = set + i;
            makeSet(user_id, banned_id, cnt + 1, nextStr, visit);
            visit[i] = false;
        }
    }
    public static boolean banned(String ban, String name) {
        int len = ban.length();
        if(len != name.length()) {
            return false;
        }
        for(int i=0;i<len;i++) {
            if(ban.charAt(i) != '*' && ban.charAt(i) != name.charAt(i)) {
                return false;
            }
        }
        return true;
    }
}