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

프로그래머스 64064문제

 

https://school.programmers.co.kr/learn/courses/30/lessons/64064?language=java 

프로그래머스

 

전처리 + 완전 탐색(조합) 문제로 판단하고 풀었다.

 

문제에서 경우의 수를 구하라고 나와있었기 때문에 경우의 수를 구할 수 있는 완전 탐색 방식을 선택하였다.

또한, 경우의 수만을 구하는 것이 중점이 아닌 불량 사용자의 아이디를 가려내는 것도 중요했기 때문에 이를 완전 탐색 직전 해야하는 전처리 작업이라고 생각하였다.

 

 

풀이 과정 1 (전처리 과정)

import java.util.*;

/**
순열로 구하기가 가능한가..?

어느 위치에 어떤 값이 들어가야한다를 2차원 배열로 표현함.
*/
class Solution {
    static boolean[] user_check;
    static List<List<Integer>> user_list;
    
    public int solution(String[] user_ids, String[] banned_id) {
        int answer = 0;
        int banned_size = banned_id.length, user_id_size = user_ids.length;
        user_check = new boolean[user_id_size];
        user_list = new ArrayList<>();
        
        for(int i = 0; i < banned_size; i++) {
            List<Integer> temp = new ArrayList<>();
            
            for(int j = 0; j < user_id_size; j++) {
                if (compare_with(banned_id[i], user_ids[j])) {
                    temp.add(j);
                }
            }
            user_list.add(temp);
        }
        
        return answer;
    }

    
    public static boolean compare_with(String banned_id, String user_id) {
        int banned_id_size = banned_id.length(), user_id_size = user_id.length();
        
        if (banned_id_size != user_id_size) {
            return false;
        }
        
        for(int i = 0; i < banned_id_size; i++) {
            if (banned_id.charAt(i) == '*' || banned_id.charAt(i) == user_id.charAt(i))
                 continue;
            return false;
        }
        return true;
    }
    
    public static
    
}

위 내용은 전처리 과정이다.

위와 같이 풀고 user_list를 예시 1을 넣고 돌려보면 아래와 같이 결과가 나온다.

아직 정답에 도달하지는 못했지만 출력값이 의미하는 바는 다음과 같다.

[0, 1]의 의미는 <"fr*d*"는 "frodo"와 "fradi" 일 수 있다>

[3]의 의미는 <"abc1**"는 "abc123" 일 수 있다>

 

풀이 과정 2 (완전 탐색)

...

class Solution {
    static List<List<Integer>> user_list;
    static int banned_size, user_id_size;
    static Set<String> user_set; // 중복제거하고 경우의 수를 구하기 위해
    static String[] user_id_s;
    
    public int solution(String[] user_ids, String[] banned_id) {
        int answer = 0;
        banned_size = banned_id.length;
        user_id_size = user_ids.length;
        user_id_s = user_ids;
        user_list = new ArrayList<>();
        user_set = new HashSet<>();

        for(int i = 0; i < banned_size; i++) {
            List<Integer> temp = new ArrayList<>();
            
            for(int j = 0; j < user_id_size; j++) {
                if (compare_with(banned_id[i], user_ids[j])) {
                    temp.add(j);
                }
            }
            user_list.add(temp);
        }
        
        combination(0, new boolean[user_id_size]);
        
        answer = user_set.size();
        return answer;
    }

    
    public static boolean compare_with(String banned_id, String user_id) {
        ...
    }
    
    public static void combination(int n, boolean[] check) {
        if (n == banned_size) {
            String temp = "";
            for(int i = 0; i < user_id_size; i++) {
                if (check[i]) {
                    temp += user_id_s[i];
                }
            }
            user_set.add(temp);
            return;
        }
        
        List<Integer> list = user_list.get(n);
        for(int i = 0, size = list.size(); i < size; i++) {
        	// 이미 경우의 수에 포함된 경우 check에서 true로 표시하고 continue
            if (check[list.get(i)])
                continue;
             
            check[list.get(i)] = true;
            combination(n + 1, check);
            check[list.get(i)] = false;
        }
    }
    
}

 

배열로 구하게 되면 하나하나 사용했는지 안했는지를 구분해야 했지만

경우의 수에 들어가는 string값들을 전부 연결해서 user_set에 String값으로 저장하게 되면 좀 더 손쉽게 중복을 제거할 수 있다.

 

전체 풀이 코드

import java.util.*;

class Solution {
    static List<List<Integer>> user_list;
    static int banned_size, user_id_size;
    static Set<String> user_set;
    static String[] user_id_s;
    public int solution(String[] user_ids, String[] banned_id) {
        int answer = 0;
        banned_size = banned_id.length;
        user_id_size = user_ids.length;
        user_id_s = user_ids;
        user_list = new ArrayList<>();
        user_set = new HashSet<>();

        for(int i = 0; i < banned_size; i++) {
            List<Integer> temp = new ArrayList<>();
            
            for(int j = 0; j < user_id_size; j++) {
                if (compare_with(banned_id[i], user_ids[j])) {
                    temp.add(j);
                }
            }
            user_list.add(temp);
        }
        
        combination(0, new boolean[user_id_size]);
        
        answer = user_set.size();
        return answer;
    }

    
    public static boolean compare_with(String banned_id, String user_id) {
        int banned_id_size = banned_id.length(), user_id_size = user_id.length();
        
        if (banned_id_size != user_id_size) {
            return false;
        }
        
        for(int i = 0; i < banned_id_size; i++) {
            if (banned_id.charAt(i) == '*' || banned_id.charAt(i) == user_id.charAt(i))
                 continue;
            return false;
        }
        return true;
    }
    
    public static void combination(int n, boolean[] check) {
        if (n == banned_size) {
            String temp = "";
            for(int i = 0; i < user_id_size; i++) {
                if (check[i]) {
                    temp += user_id_s[i];
                }
            }
            user_set.add(temp);
            return;
        }
        
        List<Integer> list = user_list.get(n);
        for(int i = 0, size = list.size(); i < size; i++) {
            if (check[list.get(i)])
                continue;
            
            check[list.get(i)] = true;
            combination(n + 1, check);
            check[list.get(i)] = false;
        }
    }
    
}

느낀 점

어떻게 전처리를 해서 완전 탐색을 돌릴지에 대해 고민하는 과정이 재밌었다.

요즘 php만 해서 자꾸 함수 선언할 때 public function으로 쓰는 바람에 여러번 지우고 다시 써서 귀찮았다.

그렇지만 처음부터 알고리즘 문제를 java로 풀었어서 그런가 java를 쓰는게 더 익숙해서 언어를 바꿀 생각은 없다!