개발팀 내에서 이벤트 개발을 담당하고 있는 무지는 최근 진행된 카카오이모티콘 이벤트에 비정상적인 방법으로 당첨을 시도한 응모자들을 발견하였습니다. 이런 응모자들을 따로 모아 불량 사용자
라는 이름으로 목록을 만들어서 당첨 처리 시 제외하도록 이벤트 당첨자 담당자인 프로도 에게 전달하려고 합니다. 이 때 개인정보 보호을 위해 사용자 아이디 중 일부 문자를 '*' 문자로 가려서 전달했습니다. 가리고자 하는 문자 하나에 '*' 문자 하나를 사용하였고 아이디 당 최소 하나 이상의 '*' 문자를 사용하였습니다.
무지와 프로도는 불량 사용자 목록에 매핑된 응모자 아이디를 제재 아이디
라고 부르기로 하였습니다.
예를 들어, 이벤트에 응모한 전체 사용자 아이디 목록이 다음과 같다면
응모자 아이디 |
---|
frodo |
fradi |
crodo |
abc123 |
frodoc |
다음과 같이 불량 사용자 아이디 목록이 전달된 경우,
불량 사용자 |
---|
frd |
abc1** |
불량 사용자에 매핑되어 당첨에서 제외되어야 야 할 제재 아이디 목록은 다음과 같이 두 가지 경우가 있을 수 있습니다.
제재 아이디 |
---|
frodo |
abc123 |
제재 아이디 |
---|
fradi |
abc123 |
이벤트 응모자 아이디 목록이 담긴 배열 user_id와 불량 사용자 아이디 목록이 담긴 배열 banned_id가 매개변수로 주어질 때, 당첨에서 제외되어야 할 제재 아이디 목록은 몇가지 경우의 수가 가능한 지 return 하도록 solution 함수를 완성해주세요.
user_id | banned_id | result |
---|---|---|
["frodo", "fradi", "crodo", "abc123", "frodoc"] | ["fr*d*", "abc1**"] | 2 |
["frodo", "fradi", "crodo", "abc123", "frodoc"] | ["*rodo", "*rodo", "******"] | 2 |
["frodo", "fradi", "crodo", "abc123", "frodoc"] | ["fr*d*", "*rodo", "******", "******"] | 3 |
큰 로직은 아래와 같다.
user_id
에서 banned_id
길이만큼 가능한 모든 조합을 구한다.banned_id
와 일치하는 지 체크한다.여기서 내가 생각해내지 못한 것은 조합을 구하는 부분이었다. 그래서 구글링을 해서 조합을 구하고 Set에 저장하고 체크하는 코드를 참고했다. Set을 사용하면 된다는 것을 알았을 때 ArrayList로 담고 이래저래 하려고 했던 내 시도가 참 한심해졌다. 앞으론 어떤 자료구조를 써야 좋을지를 먼저 생각하고 구현을 하도록 노력해야겠다.
Set이 중복 없이 element를 저장하기 좋고, 그 중 HashSet은 검색에 있어 가장 효율적인 자료구조라는 것은 알고 있었다. 하지만 HashSet과 LinkedHashSet의 차이점은 정확하게 알지 못하고 있다는 것을 이 문제를 풀면서 느꼈다. Set 인터페이스와 그 구현 클래스인 HashSet, TreeSet, LinkedHashSet에 대한 내용을 찾아 공부하고 깃헙에 정리를 했다.
import java.util.*;
class Solution {
private static String[] userId;
private static String[] bannedId;
private static Set<Set<String>> result = new HashSet<>();
public int solution(String[] user_id, String[] banned_id) {
initParams(user_id, banned_id);
dfs(new LinkedHashSet<>());
return result.size();
}
private void initParams(String[] user_id, String[] banned_id) {
userId = user_id;
bannedId = banned_id;
}
private void dfs(Set<String> set) {
if (set.size() == bannedId.length) {
if (setMatches(set))
result.add(new HashSet<>(set));
return;
}
for (String user : userId) {
if (!set.contains(user)) {
set.add(user);
dfs(set);
set.remove(user);
}
}
}
private boolean setMatches(Set<String> set) {
int i = 0;
for (String user : set)
if (!stringMatches(user, bannedId[i++]))
return false;
return true;
}
private boolean stringMatches(String user, String banned) {
if (user.length() != banned.length()) return false;
for (int i = 0; i < user.length(); i++) {
if (banned.charAt(i) == '*') continue;
if (banned.charAt(i) != user.charAt(i)) return false;
}
return true;
}
}