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

- 링크 : https://programmers.co.kr/learn/courses/30/lessons/64064?language=java 

코딩테스트 연습 - 불량 사용자

 

 

- 참고 링크 : https://bcp0109.tistory.com/186

[프로그래머스] 2019 카카오 겨울인턴. 불량 사용자 (Java)

 

- 풀이

 - 최대 배열 크기가 8 이므로 dfs로 돌아간다고 해도 d(8!) 의 경우의 수밖에 나오지 않는다.

 - 따라서 완전탐색을 고려했다.

 - 하지만 backtracking 후 데이터 이동에 대해서 생각하다가 혼자 꼬여서 실패했다.

 - banned_id의 크기만큼 user_id의 배열을 dfs을 이용해 작성, (또는 backtracking)

 - 탈출 조건 : LinkedHashSet (순서 보장) 의 크기가 banned_id와 같아졌을 때 탈출

 - 탈출 시 모든 banned_id 길이의 경우의 수가 순열조합으로 들어오기 때문에 banned_id와 LinkedHashSet의 크기가 같다면 해당 set을 resultSet에 저장해주고 마지막에 크기를 물어봤으니 resultSet의 크기를 반환해 주면 된다.

 

import java.util.*;

class Solution {    
    HashSet<HashSet<String>> resultSet = new HashSet();
    
    public int solution(String[] user_id, String[] banned_id) {
        dfs(user_id, banned_id, new LinkedHashSet<>());
        return resultSet.size();
    }
    
    private void dfs(String[] user_id, String[] banned_id, HashSet<String> set) {
        if (set.size() == banned_id.length) {
            if (isBannedUsers(set, banned_id)) {
                resultSet.add(set);
            }
            return;
        }
        
        for (String userId : user_id) {
            if (!set.contains(userId)) {
                set.add(userId);
                dfs(user_id, banned_id, set);
                set.remove(userId);
            }
        }
    }
    
    private boolean isBannedUsers(HashSet<String> set, String[] banned_id) {
        int idx = 0;
        for (String userId: set) {
            if(!isBanned(userId, banned_id[idx++])) {
                return false;
            }
        }
        return true;
    }
    
    private boolean isBanned(String userId, String bannedId) {
        if (userId.length() != bannedId.length()) {
            return false;
        }
        
        for(int i=0; i < userId.length(); i++) {
            char uc = userId.charAt(i);
            char bc = bannedId.charAt(i);
            if (bc == '*') {
                continue;
            }
            if (uc != bc) {
                return false;
            }
        }
        
        return true;
    }
}