1. 문제
문제 설명
개발팀 내에서 이벤트 개발을 담당하고 있는 무지는 최근 진행된 카카오이모티콘 이벤트에 비정상적인 방법으로 당첨을 시도한 응모자들을 발견하였습니다. 이런 응모자들을 따로 모아 불량 사용자라는 이름으로 목록을 만들어서 당첨 처리 시 제외하도록 이벤트 당첨자 담당자인 프로도 에게 전달하려고 합니다. 이 때 개인정보 보호을 위해 사용자 아이디 중 일부 문자를 '*' 문자로 가려서 전달했습니다. 가리고자 하는 문자 하나에 '*' 문자 하나를 사용하였고 아이디 당 최소 하나 이상의 '*' 문자를 사용하였습니다.
무지와 프로도는 불량 사용자 목록에 매핑된 응모자 아이디를 제재 아이디 라고 부르기로 하였습니다.
예를 들어, 이벤트에 응모한 전체 사용자 아이디 목록이 다음과 같다면
응모자 아이디
| frodo |
| fradi |
| crodo |
| abc123 |
| frodoc |
다음과 같이 불량 사용자 아이디 목록이 전달된 경우,
불량 사용자
| fr*d* |
| abc1** |
불량 사용자에 매핑되어 당첨에서 제외되어야 야 할 제재 아이디 목록은 다음과 같이 두 가지 경우가 있을 수 있습니다.
제재 아이디
| frodo |
| abc123 |
제재 아이디
| fradi |
| abc123 |
이벤트 응모자 아이디 목록이 담긴 배열 user_id와 불량 사용자 아이디 목록이 담긴 배열 banned_id가 매개변수로 주어질 때, 당첨에서 제외되어야 할 제재 아이디 목록은 몇가지 경우의 수가 가능한 지 return 하도록 solution 함수를 완성해주세요.
[제한사항]
- user_id 배열의 크기는 1 이상 8 이하입니다.
- user_id 배열 각 원소들의 값은 길이가 1 이상 8 이하인 문자열입니다.
- 응모한 사용자 아이디들은 서로 중복되지 않습니다.
- 응모한 사용자 아이디는 알파벳 소문자와 숫자로만으로 구성되어 있습니다.
- banned_id 배열의 크기는 1 이상 user_id 배열의 크기 이하입니다.
- banned_id 배열 각 원소들의 값은 길이가 1 이상 8 이하인 문자열입니다.
- 불량 사용자 아이디는 알파벳 소문자와 숫자, 가리기 위한 문자 '*' 로만 이루어져 있습니다.
- 불량 사용자 아이디는 '*' 문자를 하나 이상 포함하고 있습니다.
- 불량 사용자 아이디 하나는 응모자 아이디 중 하나에 해당하고 같은 응모자 아이디가 중복해서 제재 아이디 목록에 들어가는 경우는 없습니다.
- 제재 아이디 목록들을 구했을 때 아이디들이 나열된 순서와 관계없이 아이디 목록의 내용이 동일하다면 같은 것으로 처리하여 하나로 세면 됩니다.
[입출력 예]
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 |
입출력 예에 대한 설명입출력 예 #1
문제 설명과 같습니다.
입출력 예 #2
다음과 같이 두 가지 경우가 있습니다.
제재 아이디
| frodo |
| crodo |
| abc123 |
제재 아이디
| frodo |
| crodo |
| frodoc |
입출력 예 #3
다음과 같이 세 가지 경우가 있습니다.
제재 아이디
| frodo |
| crodo |
| abc123 |
| frodoc |
제재 아이디
| fradi |
| crodo |
| abc123 |
| frodoc |
제재 아이디
| fradi |
| frodo |
| abc123 |
| frodoc |
2. 내풀이
package Programmers.Baduser;
import java.util.ArrayList;
import java.util.HashMap;
import java.util.HashSet;
import java.util.Stack;
class Combination<T> {
private T[] arr; //기준 배열
private Stack<T> st; //조합을 저장할 스택
public ArrayList<ArrayList<T>> result = new ArrayList<>();
public Combination(T[] arr) {
this.arr = arr; //배열을 받아 객체에 저장한다.
st = new Stack<T>(); //스택에 메모리를 할당한다.
}
public void addStack() {
//스택에 있는 값들을 출력한다.
ArrayList<T> arrayList = new ArrayList<>();
for (int i = 0; i < st.size(); i++) {
//System.out.print(st.get(i) + " ");
arrayList.add(st.get(i));
}
result.add(arrayList);
}
public ArrayList<ArrayList<T>> doCombination(int n, int r, int index) {
// n : 전체 개수
// r : 뽑을 개수
// index 배열이다보니 현재 배열의 어디를 가리키고 있는지 필요하므로.
if (r == 0) {
//0개를 뽑는다는건 더 이상 뽑을 것이 없다는 말과 같으므로 스택을 출력하고 함수를 종료한다.
addStack();
return result;
} else if (n == r) {
//nCr 이라는 건 나머지를 전부 뽑겠다는 말과 같으므로 전부 스택에 넣은 후 출력하면 된다.
for (int i = 0; i < n; i++) st.add(arr[index + i]);//index부터 n개를 차례대로 스택에 넣고
addStack(); //결과에 넣여준다.
for (int i = 0; i < n; i++) st.pop(); //이후 전부 pop을 시켜 다음 과정을 진행한다.
} else {
//저 두가지 예외 사항을 빼면 점화식대로 진행하면 된다.
//index를 포함하는 경우
st.add(arr[index]);
doCombination(n - 1, r - 1, index + 1); //index를 스택에 넣은상태로 index를 1옮겨 그대로 진행.
//index를 포함하지 않는 경우
st.pop(); //index를 제거해주고
doCombination(n - 1, r, index + 1); //index를 제외한 상태에서 n-1Cr 진행.
}
return result;
}
// public static void main(String[] args) {
// String[] arr = {"rho", "doo", "hyun"};
// Integer[] arrant = {1, 2, 3};
// Combination combination = new Combination(arr);
// ArrayList<ArrayList<String>> arrayLists = combination.doCombination(arr.length, 2, 0);
// for (int i = 0; i < arrayLists.size(); i++) {
// for (int j = 0; j < arrayLists.get(i).size(); j++) {
// System.out.print(arrayLists.get(i).get(j) + " ");
// }
// System.out.println();
// }
//
// }
}
class Baduser {
public boolean compareString(String A, String B) {
char[] banID = B.toCharArray();
if (A.length() == banID.length) {
char[] userID = A.toCharArray();
String stars = "";
for (int k = 0; k < banID.length; k++) {
stars += "*";
}
// bannid가 ******이면 글자수가 맞으니까 통과
if (stars.equals(B)) return true;
for (int k = 0; k < banID.length; k++) {
if (banID[k] == '*') continue;
// 글자 수가 안맞으면
if (banID[k] != userID[k]) return false;
}
// 문자열이 조건이 맞으므로 List에 추가
return true;
}
return false;
}
public int solution(String[] user_id, String[] banned_id) {
int answer = 0;
Combination combination = new Combination(user_id);
ArrayList<ArrayList<String>> arrayLists = combination.doCombination(user_id.length, banned_id.length, 0);
for (int i = 0; i < arrayLists.size(); i++) {
int count = 0;
for (int j = 0; j < banned_id.length; j++) {
String A = arrayLists.get(i).get(j);
if (compareString(A, banned_id[j])) count++;
}
if (count == banned_id.length) answer++;
}
return answer;
}
public static void main(String[] args) {
Baduser solution = new Baduser();
String[] user_id = {"frodo", "fradi", "crodo", "abc123", "frodoc"};
String[] banned_id = {"fr*d*", "*rodo", "******", "******"};
System.out.println(solution.solution(user_id, banned_id));
}
}
- 못풀었다. 생각은 해내었다.
1. userid에서 banid의 갯수만큼 골라서 조합하고 순열하여 모든 경우의 경우를 ArrayList<ArrayList<String>>에 저장한다.
2. 모든 경우의 수를 banid와 하나씩 비교하여 조건이 되는지 보고 조건이 된다면 answer ++
3. answer 반환
... 굉장히 무식한 방법이다. 일단 java는 python과 다르게 조합과 순열이 내부함수에 없다. 그래서
그 모든 조합을 항상 직접개발해야하는데, 모든 조합을 구하는 combination 함수(순열이 아닌)를 generic 함수를 이용해서 구현하였고 다음 순열하여 모든 경우의 수를 구하려다가 시간적소모와 비효율적인 코드가 아닌것같아서 그만두었다.
3. 다른 사람 풀이
package Programmers.Baduser;
import java.util.HashSet;
import java.util.regex.Pattern;
class Baduser {
private String[] userId;
private String[] bannedRegex;
private boolean[] checked;
private HashSet<HashSet<Integer>> resultSet;
public int solution(String[] user_id, String[] banned_id) {
userId = user_id;
checked = new boolean[user_id.length];
resultSet = new HashSet<>();
bannedRegex = new String[banned_id.length];
for (int i = 0; i < banned_id.length; i++) {
bannedRegex[i] = banned_id[i].replace("*", ".");
}
dfs(0, new HashSet<>());
return resultSet.size();
}
private void dfs(int index, HashSet<Integer> set) {
// 가장깊이 들어가서 더 탐색할 bannedRegex가 없다면 HashSet의 결과를 넣는다.
if (index == bannedRegex.length) {
resultSet.add(set);
return;
}
// 유저의 길이 만큼 탐색한다.
for (int i = 0; i < userId.length; i++) {
// bannedId의 조건에 userId가 만족할 경우 그리고 유저아이디가 한번도 탐색하지 않았을 경우
if (Pattern.matches(bannedRegex[index], userId[i]) && !checked[i]) {
// 해당 유저는 탐색을 해본 경우이므로 체크
checked[i] = true;
// set에 탐색을 한 경우를 추가한다.
set.add(i);
// banned_id를 한칸 더 들어가서 탐색한다.
dfs(index + 1, new HashSet<>(set));
// 해당 유저보다 깊은 곳은 탐색을 마쳤으므로
// 다시 돌아가서 다음 유저를 탐색하기 위해 checked 배열 과 Hashset을 초기화한다.
checked[i] = false;
set.remove(i);
}
}
}
public static void main(String[] args) {
Baduser solution = new Baduser();
String[] user_id = {"frodo", "fradi", "crodo", "abc123", "frodoc"};
String[] banned_id = {"fr*d*", "*rodo", "******", "******"};
System.out.println(solution.solution(user_id, banned_id));
}
}
- 정규표현식으로 특정 문자열을 걸러낼 수 있다. (Patttern, Matcher 클래스)
- dfs로 조합순열을 구현할 수 있다.
- HashSet<HashSet<Integer>>로 중복을 걸러낼 수 있다.
4. Tip
- java는 조합이 구현되어 있지 않다. dfs로 모든 경우의 수마다 걸러서 구현하자
- 정규표현식을 사용하여 쉽게 문자를 걸러낼수 있다.
'알고리즘 > Programers' 카테고리의 다른 글
| Programmers - Greedy [큰 수 만들기] (0) | 2020.11.12 |
|---|---|
| Programmers - [풍선터트리기] (0) | 2020.11.06 |
| Programmers - Hash [베스트 앨범] (0) | 2020.11.01 |
| Programmers - 완전탐색 [카펫] (0) | 2020.10.30 |
| Programmers - 완전탐색 [소수찾기] (0) | 2020.10.29 |
