[프로그래머스] LV 3 불량사용자

https://school.programmers.co.kr/learn/courses/30/lessons/64064#qna

프로그래머스

접근 방법

• 1  <= id의 길이 <= 8
• 1<= banned_id.length <= user_id.length <= 8
• 인풋값이 매우 적어 백트래킹으로 풀었다.
• 먼저, user_id가 banned_id를 파라미터로 받아서 제재되어야하는지 판단하는 함수를 만들었다
• 해당 함수를 기반으로 String 순열을 list에 담는다.
  
  • 조합으로 할때, 조건에따라 이전 idx의 데이터가 건너뛰어지는 경우가 생김
  • 순열로 모든 경우의 수를 뽑고 공통을 제거하는것이 편하다고 생각
• 순열로 얻은 String 리스트를 정렬하여 set을 통해 같은 원소를 가진 배열을 필터링한다
  • 필터링할때 배열을 그대로 사용하면 안되고 List로 바꾸어 사용해야한다
  • 배열은 equals, hashcode 등이 주소값을 기반으로 동작하여 set에서 걸러지지 않는다
  • List는 각 원소의 값이 같으면 hashcode도 같고 equals도 같게 동작하여 set에서 걸러진다

코드

import java.util.*;
class Solution {
    int n,m;
    List<String[]> list = new ArrayList<>();
    String[] uid,bid;
    public int solution(String[] user_id, String[] banned_id) {
        n = user_id.length;
        m = banned_id.length;
        uid= user_id;
        bid= banned_id;
        
        bt(0, new String[m], new boolean[n]);
        
        Set<List<String>> set = new HashSet<>();
        List<String[]> ans = new ArrayList<>();

        for (String[] s : list) {
            List<String> sortedList = Arrays.asList(s);
            Collections.sort(sortedList);

            if (set.add(sortedList)) {
                ans.add(s);
            }
        }
        return ans.size();
    }
    void bt(int depth, String[] sel, boolean[] isUsed){
        if(depth == m){
            list.add(Arrays.copyOf(sel, sel.length));
            return;
        }
        
        for(int i = 0 ; i < n ; i++){
            if(isUsed[i])continue;
            if(eqString(uid[i], bid[depth])){
                isUsed[i] = true;
                sel[depth] = uid[i];
                comb(depth+1,sel, isUsed);
                isUsed[i] = false;
            }
        }
    }
    boolean eqString(String a,String b){
        if(a.length() != b.length()) return false;
        
        for(int i = 0 ; i < a.length() ; i++){
            if(b.charAt(i) == '*') continue;
            if(a.charAt(i) != b.charAt(i)) return false;
        }
        return true;
    }
}