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

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

프로그래머스

 

 

2019 카카오 개발자 겨울 인턴십 Level 3 완전탐색 문제다.

 

처음에는 황당할 정도로 비효율적이고 복잡하게 구현했다. 물론 맞히긴 했지만..

제재 아이디와 사용자 아이디가 매핑되는 모든 조합을 구하고, hashset을 통해 중복 검사해 set의 사이즈를 return 했다.

 

제재 아이디와 사용자 아이디를 먼저 조합하는 것보단,

dfs를 통해 사용자 아이디를 완전탐색 한 후 선택된 사용자 아이디 size와 제재 아이디의 size와 같다면

모두 매핑되어 있는지 확인하면 된다.

그리고 중복된 경우가 있을수 있으므로 그 경우를 hashset에 저장한 후,

결과를 저장한 hashset의 사이즈를 return 한다.

 

 

https://docs.oracle.com/en/java/javase/16/docs/api/java.base/java/util/HashSet.html#add(E) 

HashSet (Java SE 16 & JDK 16)

그리고 hashset의 add함수가 반환값이 있다는 것을 이 문제를 풀며 알게 됐다.

add(x)일 때 set에 x가 이미 존재한다면 false, 존재하지 않는다면 true를 반환한다.

앞으로 값 체크할 때 contains보다 add를 활용하면 더 깔끔할 것 같다.

 

 

import java.util.HashSet;
import java.util.LinkedHashSet;

class Solution {
	static HashSet<HashSet<String>> ans = new HashSet<>();

	static int solution(String[] user_id, String[] banned_id) {
		DFS(new LinkedHashSet<>(), user_id, banned_id);

		return ans.size();
	}

	static void DFS(HashSet<String> set, String[] user_id, String[] banned_id) {
		if(set.size() == banned_id.length) {
			if(isMapping(set, banned_id))
				ans.add(new HashSet<>(set));
			return;
		}

		for(String str : user_id) {
			if(set.add(str)) {
				DFS(set, user_id, banned_id);
				set.remove(str);
			}
		}

	}

	static boolean isMapping(HashSet<String> set, String[] banned_id) {
		int idx = 0;
		for(String str : set) {
			if(str.length() != banned_id[idx].length())
				return false;
			for(int i=0;i<banned_id[idx].length();i++) {
				if(banned_id[idx].charAt(i) == '*')
					continue;
				if(str.charAt(i) != banned_id[idx].charAt(i))
					return false;
			}
			idx++;
		}
		return true;
	}

}

 

 

참고

https://dding9code.tistory.com/105