불량 사용자
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 시켜주는 방법으로 해야했다.