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

문제 링크

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

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

풀이

 문제를 풀기 위한 과정은 다음과 같다.

1. 아이디 리스트 중 차단 사용자 목록 개수 만큼 조합 생성
2. 생성된 아이디 조합에서 모든 경우의 수를 확인하여 차단 사용자 목록과 매칭이 되는 지를 확인 (정규표현식 활용)

 처음 문제 알고리즘을 작성했을 땐 단순히 재귀를 통해 무작정 banned_id와 매칭을 진행하고 결과를 반환했지만, 이 경우 문제 요구 중 하나인 '제재 아이디 목록들을 구했을 때 아이디들이 나열된 순서와 관계없이 아이디 목록의 내용이 동일하다면 같은 것으로 처리하여 하나로 세면 됩니다' 라는 부분으로 아이디 조합을 생성해서 검증을 하는 것으로 방향을 바꾸었다. 결국 전체적으로 문제 풀이 자체는 쉽지만, 자바 특성 상 조합/순열 같은 경우의 수 계산 함수 자체가 없어 이를 함수로 직접 작성하는데 어려운 문제였다.

 전체적인 문제 풀이의 흐름은 우선 주어진 banned_id를 정규표현식에 맞게 '*'을 '.'으로 변경하고, 조합에서 사용할 visited 배열을 선언 후, 주어진 userIds들에 대한 banned_id 개수만큼의 조합을 생성한다. 이후 매번 아이디 조합이 생성될 때마다 해당 아이디 조합과 차단 사용자 목록 사이의 검증을 거치는 데, 이 때 서로 간의 순서 차이로 매칭 되는게 안될 수도, 안되는게 될 수도 있기 때문에 이런 경우엔 순열을 활용하여 가능한 모든 경우의 수를 통해 매칭의 결과를 검증한다. 이후 검증의 결과가 참이라면 답을 하나 증가시켜 결과적으로 답을 반환한다.

class Solution {
    String[] user_id, banned_id;
    int answer = 0;

    public int solution(String[] user_id, String[] banned_id) {
        for (int i = 0; i < banned_id.length; i++) {//정규표현식에 맞게 *을 .으로 변경
            banned_id[i] = banned_id[i].replace('*', '.');
        }

        this.user_id = user_id;
        this.banned_id = banned_id;

        boolean[] visited = new boolean[user_id.length];

        combination(visited, 0, user_id.length, banned_id.length);

        return answer;
    }

    private void combination(boolean[] visited, int start, int n, int r) {//리스트 중 유저 아이디 조합 생성
        if (r == 0) {
            String[] userIds = new String[banned_id.length];

            for (int i = 0, j = 0; i < visited.length; i++) {
                if(visited[i]){
                    userIds[j++] = user_id[i];
                }
            }

            if(validate(userIds, banned_id.length))//검증 확인
                ++answer;

        } else {
            for (int i = start; i < n; i++) {
                visited[i] = true;
                combination(visited, i + 1, n, r - 1);
                visited[i] = false;
            }
        }
    }

    private boolean validate(String[] userIds, int r){//주어진 조합이 banned_id에 맞는 지 확인
        int[] list = new int[r];

        for (int i = 0; i < r; i++)
            list[i] = i;

        do {//순열을 통해 모든 경우의 수 체크
            int matchCount = 0;

            for (int i = 0; i < banned_id.length; i++) {
                if (Pattern.matches(banned_id[i], userIds[list[i]]))
                    ++matchCount;
                else
                    break;
            }

            if (matchCount == r)//사용자 목록이 모두 banned_id와 매칭되면 true 반환
                return true;

        } while (next_permutation(list));

        return false;//매칭 안되는 걸로 false 반환
    }

    private boolean next_permutation(int[] list) {//다음 순서의 순열로 리스트 교체
        int i = list.length - 1;
        int j = list.length - 1;

        while (i > 0 && list[i - 1] >= list[i])
            --i;

        if (i <= 0)
            return false;

        while (list[i - 1] > list[j])
            --j;

        swap(list, i - 1, j);

        j = list.length - 1;
        for (; i < j; ++i, --j)
            swap(list, i, j);

        return true;
    }

    private void swap(int[] list, int i, int j) {//swap 함수
        int temp = list[i];
        list[i] = list[j];
        list[j] = temp;
    }
}

결과