[프로그래머스 2019 카카오 개발자 겨울 인턴십] 불량 사용자 -Java

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

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

import java.util.HashSet;
import java.util.PriorityQueue;
class Solution {
		int answer;
		PriorityQueue<String> pq;
		HashSet<String> hs;
	    public int solution(String[] user_id, String[] banned_id) {
	    	answer=0;
	        boolean visited[]=new boolean[user_id.length];
	        pq=new PriorityQueue<>((o1,o2)->(o1.compareTo(o2)));
	        hs= new HashSet<String>();
	        
	        dfs(user_id, banned_id,visited,0);
	        
	        return answer;
	    }
		private void dfs(String[] user_id, String[] banned_id, boolean[] visited, int cnt) {
			if(cnt==banned_id.length) {
				
				String str=duplicateCheck(user_id,visited);
				if(hs.contains(str)) return;
				else hs.add(str);
				answer++;
				return ;
			}
			
			String ban=banned_id[cnt];
			
			for(int i=0; i<user_id.length; i++) {
				if(visited[i]) continue;
				if(check(user_id[i],ban)) { //벤 이 맞을 때 
					visited[i]=true;
					dfs(user_id, banned_id, visited, cnt+1);
				}
				visited[i]=false;
			}
			
		}
		private String duplicateCheck(String[] user_id, boolean[] visited) {
			String out="";
			for(int i=0; i<user_id.length; i++) {
				if(visited[i]) pq.offer(user_id[i]);
			}
			int size=pq.size();
			for(int i=0; i<size; i++) {
				out+=pq.poll();
			}
			return out;
		}
		private boolean check(String user, String ban) {
			if(user.length()!=ban.length()) return false;
			
			for(int i=0; i<user.length(); i++) {
				if(ban.charAt(i)=='*') continue;
				if(user.charAt(i)!=ban.charAt(i)) return false;
			}
			return true;
		}
	}

소요시간 : 45분

 

일단은 DFS로 풀었습니다! 조합과 코드가 거의 비슷합니다~

DFS를 돌면서 ban의 길이만큼 cnt가 만들어지면 visited배열의 true값을 체크해 선택된 user_id를 확인합니다

위 상황처럼 ban길이만큼 cnt가 만들어 지면  중복을 처리하기 위해 우선순위큐와, HashSet을 사용합니다.

예를들어

frodo   crodo
crodo   frodo  와 같은 경우는 순서만 다르지 사실상 제재된 경우의 수는 똑같기 때문입니다.

 

두 경우 모두 우선순위큐에 넣어줍니다. 그리고 우선순위큐에서 하나씩 빼면서 글자를 더해줍니다.

그리고 더해진 글자를 HashSet에 넣어서 있는지 없는지 확인해주면 중복검사는 끝입니다!