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

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

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

 

문제

비정상적인 방법으로 당첨을 시도한 응모자들을 골라내기 위해 불량 사용자 목록에 들어갈 수 있는 응모자 아이디의 경우의 수를 구하는 문제입니다.

응모자 아이디가 user_id로 주어지고, 불량 사용자 아이디 목록이 banned_id로 주어집니다.

주어진 예시로 살펴보면 응모자 아이디와 불량 아이디 목록이 이렇게 주어질 것입니다.

 

'*'는 문자 하나에 해당합니다. 나올 수 있는 불량 사용자 목록을 살펴보면 아래와 같이 2가지의 경우의 수가 나옵니다.

 

 

 

풀이

정규표현식과 비트마스킹을 이용해 DFS를 사용하여 풀었습니다.

 

우선, 각각의 불량 사용자 아이디에 해당될 수 있는 아이디 목록을 저장했습니다.

불량 아이디 목록의 size를 가진 ArrayList배열 list를 생성한 후,

list에 아이디 자체를 저장하지 않고 주어진 user_id 의 인덱스를 저장하였습니다. 

 

list배열의 0인덱스를 시작점으로 두고, 아이디를 하나씩 선택해가면서 DFS로 탐색을 합니다.

문제에서 "제재 아이디 목록들을 구했을 때 아이디들이 나열된 순서와 관계없이 아이디 목록의 내용이 동일하다면 같은 것으로 처리하여 하나로 세면 됩니다." 라는 조건이 있었습니다.

비트마스킹을 이용하면 DFS로 탐색할 때, 아이디가 이미 선택되어 리스트에 저장되었는지 확인할 수 있고 동시에 편하게 완성된 제재 아이디 리스트의 중복도 확인할 수 있습니다.

완성된 제재 아이디 리스트는 numbers라는 리스트에 넣어 확인하였습니다.

 

 

Code

import java.util.*;
import java.util.regex.Pattern;

class Solution {
    	
	static int tot, len1, len2, bit;
	static ArrayList<Integer>[] list;
	static ArrayList<Integer> numbers;
	
	public static int solution(String[] user_id, String[] banned_id) {
		
		len1 = user_id.length;
		len2 = banned_id.length;
		list = new ArrayList[len2];
		numbers = new ArrayList<>();
		
		for(int i=0; i<len2; i++) {
			list[i] = new ArrayList<>();
		}
		
		for(int i=0; i<len2; i++) {
			String str = banned_id[i].replaceAll("[*]", "."); //정규표현식 문장으로 변환
			Pattern pattern = Pattern.compile(str);
			
			for(int j=0; j<len1; j++) {
				if(Pattern.matches(str, user_id[j])) { 
					list[i].add(j); //i번째의 제재아이디에 포함되는 아이디의 idx 넣기
				}
			}
		}

		for(int i=0; i<len2; i++) {
			bit = 0;
			dfs(i, 0);
		}

        return tot;
    }
	
	private static void dfs(int start, int cnt) {
		
		if(start == len2) {
			if(cnt==len2 && !numbers.contains(bit)) {
				tot++;
				numbers.add(bit);
			}
			return;
		}
		
		for(int i=0; i<list[start].size(); i++) {
			int check = list[start].get(i);
			
			if((bit&(1<<check))==0) {
				bit|=(1<<check); //check번째 비트 켜기
				dfs(start+1, cnt+1);
				bit&=~(1<<check); //check번째 비트 끄기
			}
		}
	}
}