[ 알고리즘 ] 코딩 - Programmers - 불량 사용자.java

---

문제 링크

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

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

 

---

* Programmers - 2019 카카오 개발자 겨울 인턴십

* - Level 3 - (자바) 불량 사용자 - DFS / HashSet을 이용한 중복제거 

입출력 예시

 

---

< 로직 >

1. DFS를 수행하며 일반과 불량 사이의 모든 경우의 수를 찾는다

2. 선택 중 중복을 제거하기 위해 HashSet을 이용한다

2 - 1. DFS와 visited배열로 방문 체크를 하며 반복 순회하는데 불량 사용자의 아이디가 

모두 *로 가려진 경우에는 중복 선택을 하게된다. 이를 제거하는 것이 핵심

3. HashSet의 길이가 곧 정답!

로직 예시

 

---

import java.util.HashSet;
class Solution {
    private static HashSet<String> ban_user_idx;
	    public int solution(String[] user_id, String[] banned_id) {
	    	boolean visited[] = new boolean[user_id.length]; // 방문체크
	    	ban_user_idx = new HashSet<String>(); // 중복제거
	    	dfs(user_id, banned_id, 0, visited); // 경우의 수 찾기
	        int answer = ban_user_idx.size();
	        return answer;
	    }

		private void dfs(String[] user_id, String[] banned_id, int ban_idx, boolean[] visited) {
			if(ban_idx == banned_id.length) { // ban된 id 모두 선택
				StringBuilder user_idxs = new StringBuilder();
				for(int i = 0; i < user_id.length; i++) {
					if(visited[i]) {
						user_idxs.append(i); // 모든 인덱스를 이어붙이자
					}
				}
				ban_user_idx.add(user_idxs.toString()); // 중복된 값 없는 모든 인덱스
				return ;
			}
			for(int i = 0; i < user_id.length; i++) {
				if(visited[i]) continue;
				boolean flag = false;
                                // 유저와 밴 된 유저의 길이가 같은 경우만 체크
				if(user_id[i].length() == banned_id[ban_idx].length()) {
					for(int s = 0; s < user_id[i].length(); s++) {
						if(banned_id[ban_idx].charAt(s) == '*') continue;
                                               // 하나라도 다른 글자가 포함되어 있다면 멈추고 다음 유저로
						if(user_id[i].charAt(s) != banned_id[ban_idx].charAt(s)) {
							flag = true;
							break;
						}
					}
					if(!flag) { // 모든 글자가 맞았다
						visited[i] = true;
						dfs(user_id, banned_id, ban_idx+1, visited); // 다음 탐색
						visited[i] = false;
					}
				}
			}
		}
}