알고리즘/프로그래머스
[프로그래머스] 불량 사용자 Java 풀이 및 해설
승민아
2024. 5. 11. 15:46
https://school.programmers.co.kr/learn/courses/30/lessons/64064
풀이 방법
banned_id를 반복문으로 돌며
일치하는 user_id를 하나씩 밴한다.
그리고 유저들의 인덱스를 가지고
밴을 당했다면 1 안당했다면 0으로 String을 만들어 중복된 밴 목록인지 체크하면된다.
전체 코드
import java.util.*;
class Solution {
public void dfs(int idx, String[] user_id, String[] banned_id, boolean[] visit, Map<String, Boolean> m) {
// 밴을 모두 했다면
if(idx==banned_id.length) {
String str = "";
for(int i=0; i<visit.length; i++) {
if(visit[i])
str += "1";
else
str += "0";
}
// 중복된 밴 목록인지 확인
if(m.get(str) == null)
m.put(str, true);
return;
}
for(int i=0; i<user_id.length; i++) {
if(isSame(user_id[i], banned_id[idx]) && !visit[i]) {
visit[i] = true;
dfs(idx+1, user_id, banned_id, visit, m);
visit[i] = false;
}
}
}
public int solution(String[] user_id, String[] banned_id) {
boolean[] visit = new boolean[user_id.length];
Map<String, Boolean> m = new HashMap<>();
dfs(0, user_id, banned_id, visit, m);
return m.size();
}
public boolean isSame(String userId, String bannedId) {
if(userId.length() != bannedId.length())
return false;
for(int i=0; i<userId.length(); i++) {
// "*" 가 아닌 문자라면 비교
if(bannedId.charAt(i) != '*' && userId.charAt(i) != bannedId.charAt(i)) {
return false;
}
}
return true;
}
}