Life Engineering
[프로그래머스] 불량 사용자 (Java) 본문
https://programmers.co.kr/learn/courses/30/lessons/64064
import java.util.*;
class Solution {
static Set<String> set=new HashSet<>();
static ArrayList<ArrayList<String>> li=new ArrayList<>();
public int solution(String[] user_id, String[] banned_id) {
for (int i=0; i<banned_id.length; i++){
li.add(new ArrayList<>());
findString(i, user_id, banned_id[i]);
}
dfs(0, banned_id.length, new String[banned_id.length]);
return set.size();
}
public void dfs(int num, int size, String[] arr){
if (num==size){
String[] temp=Arrays.copyOf(arr, size);
Arrays.sort(temp);
StringBuilder sb=new StringBuilder("");
for (String s: temp){
sb.append(s);
}
set.add(sb.toString());
return;
}
for (int i=0; i<li.get(num).size(); i++){
String s=li.get(num).get(i);
boolean flag=false;
for (int j=0; j<num; j++){
if (s.equals(arr[j])){
flag=true;
break;
}
}
if (flag) continue;
arr[num]=s;
dfs(num+1, size, arr);
}
}
public void findString(int num, String[] user_id, String ban){
for (String uid : user_id){
if (uid.length()==ban.length()){
boolean flag=true;
for (int i=0; i<uid.length(); i++){
if (ban.charAt(i)!='*' && ban.charAt(i)!=uid.charAt(i)){
flag=false;
break;
}
}
if (flag){
li.get(num).add(uid);
}
}
}
}
}
정규표현식을 이용했더라면 더 간단했을.. 백트래킹 문제.
findString()에서 각 banned_id와 일치하는 후보군들을 모두 저장해준다.
이후 dfs()에서 그 후보군의 가능한 경우를 뽑은 뒤, 중복되는 거 제외(이전까지 for 문 돌려서..) 한 후, 뽑은 문자열들을 정렬해서 set에 넣어주는 형태로 했다.
하지만 다른 분들의 코드를 보니, 더 간단하게 풀 수 있다. (https://moonsbeen.tistory.com/45)
regex[i] = banned_id[i].replace("*", "."); 로 정규표현식 형태로 바꿔준 뒤,
banned_id 마다, user_id를 쫙 돌면서 일치하고(이때 matches를 써준다), 미방문인(중복을 피하기 위해) 것들을 string에 넣어주고, 최종적으로 중복되는 것을 피하기 위해 set에 넣는다.
'Problem Solving' 카테고리의 다른 글
[프로그래머스] 길 찾기 게임 (Java) (0) | 2022.03.25 |
---|---|
[BOJ 2133] 타일 채우기 (Java) (0) | 2022.03.25 |
[BOJ 19238] 스타트 택시 (Java) (0) | 2022.03.23 |
[BOJ 1918] 후위 표기식 (Java) (0) | 2022.03.22 |
[BOJ 1967] 트리의 지름 (Java) (0) | 2022.03.22 |