Close
Close full mode
logo만렙 개발자 키우기

불량 사용자

Git RepositoryEdit on Github
Last update: a year ago by nowwaterReading time: 2 min

문제

코드

코드 보기
import java.util.*;
public class intern20193 {
public static void main(String[] args) {
Solution sol = new Solution();
Scanner sc = new Scanner(System.in);
int n = sc.nextInt(), m =sc.nextInt();
String user[] = new String[n], ban[] = new String[m];
for (int i = 0; i < n; i++)
user[i] = sc.next();
for (int i = 0; i < m; i++)
ban[i] = sc.next();
System.out.println(sol.solution(user, ban));
}
}
class Solution{
public int solution(String[] user_id, String[] banned_id) {
int n = user_id.length, m = banned_id.length, ans = 0;
for (int num = (1 << n) - 1; num > 0 ; --num) {
List<String> names = new ArrayList<>();
for (int i = 0; (1 << i) <= num; i++) {
if(((1 << i) & num) > 0)
names.add(user_id[i]);
}
if(names.size() != m) continue;
boolean visited[] = new boolean[m];
for (int j = 0; j < m; j++) {
if(isMatched(names.get(0), banned_id[j])){
visited[j] = true;
if(count(1, names, banned_id, visited)) {
ans += 1;
break;
}
visited[j] = false;
}
}
}
return ans;
}
private boolean count(int num, List<String> users, String[] bans, boolean[] visited) {
if(num >= bans.length)
return true;
String here = users.get(num);
for (int i = 0; i < bans.length; i++) {
if(visited[i]) continue;
if(isMatched(here, bans[i])){
visited[i] = true;
if(count(num + 1, users, bans, visited))
return true;
visited[i] = false;
}
}
return false;
}
private boolean isMatched(String s, String line) {
if(s.length() != line.length()) return false;
for (int i = 0; i < line.length(); i++) {
if(s.charAt(i) == line.charAt(i) || line.charAt(i) == '*') continue;
return false;
}
return true;
}
}

⭐️느낀점⭐️

처음에 보고 뭔소린가 이해가 안되서 다음 문제로 넘어갔었는데, 뒤로 갈수록 난이도가 증가하는 것 같다. 무조건 앞에서부터 풀고 넘어가야 시간낭비를 안할 듯 하다.

조합탐색이 할 때 마다 한번에 매끄럽게 바로 풀리지 않는 것 같다. 비트마스킹 부분을 좀더 보완해야겠다.

풀이 📣


1️⃣ 유저 아이디 목록 중 패턴의 개수만큼 뽑아낸다.

- 조합 탐색을 실시해서 LSB = 1 부터 MSB = 1까지 모든 비트마스크를 만들어서 패턴의 개수만큼 가지는 비트마스크를 찾아낸다.
- 패턴의 개수와 일치하는 비트마스크로 유저 아이디의 인덱스를 뽑아서 문자열 리스트로 만들어준다.

2️⃣ 선택한 유저 아이디들로 패턴에 일치시킬 수 있는지 확인한다.

- 매핑되는 순서는 중요하지 않기 때문에, 어느 경우라도 일치하기만 하면 true 를 반환한다.

3️⃣ 만약 패턴에 일치하면 정답을 1만큼 증가시켜준다.

4️⃣ 구한 정답을 출력한다.


실수 😅

  • Set 을 이용해서 일치하는 경우에 선택한 아이디들을 저장해놓고, 중복 탐색을 방지하려고 했었다.

  • 그렇게 되면 Set 에 문자열 리스트 또는 한 줄로 압축한 문자열을 저장해야 하는데 비효율적이다.

  • 따라서 따로 완성한 문자열 리스트를 저장할 필요 없이 모든 경우에 대해 한번씩만 탐색해보고 일치하면 정답을 +1 시켜주는 방법으로 해야했다.

👩‍💻 Problem Solving — Previous
튜플
Next — 👩‍💻 Problem Solving
호텔 방 배정