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

카테고리

DFS

나만의 카테고리

DFS, SET

문제 링크

programmers.co.kr/learn/courses/30/lessons/64064

요점

• Set 사용 방법과 특징에 대해 알아야 좋다
• DFS 방식에 대해 알아야한다
• 꼭 정규식을 사용하지 않아도 되지만 유용하다

참고 지식

• Set 메서드
• 정규식

풀이 (Java)

import java.util.regex.Pattern;
import java.util.*;

class Solution {
    private int bannedIdSize;
    private HashSet<HashSet<String>> result = new HashSet<>();
    
    public int solution(String[] user_id, String[] banned_id) {
        bannedIdSize = banned_id.length;
        int answer = 0;
        
        List<Set<String>> matchedIdList = new ArrayList<>();
        
        for (String bannedId : banned_id) {
            HashSet<String> userSet = new HashSet<>();
            for (String userId : user_id) {
                if (isMatchedId(userId, bannedId)) {
                    userSet.add(userId);
                }
            }
            
            matchedIdList.add(userSet);
        }
        
        int index = 0;
        dfs(index, matchedIdList, new HashSet<>());
        answer = result.size();
        
        return answer;
    }
    
    public void dfs(int index, List<Set<String>> matchedIdList, HashSet<String> userSet) {
        if (userSet.size() == bannedIdSize) {
            result.add(new HashSet<>(userSet));
            
            return;
        }
        
        for (String userId : matchedIdList.get(index)) {
            if (!userSet.contains(userId)) {
                userSet.add(userId);
                dfs(index + 1, matchedIdList, userSet);
                userSet.remove(userId);
            }
        }
    }
    
    public boolean isMatchedId(String userId, String bannedId) {
        String bannedPattern = bannedId.replace("*", ".");
        return Pattern.matches(bannedPattern, userId);
    }
}

 

1) 정규식을 이용해 각 패턴에 맞는 사용자 Set을 뽑는다.

2) DFS 식에서 패턴에 맞는 사용자를 순회해서 Set을 뽑는다.

3) DFS로 뽑은 Set의 갯수를 반환한다

 

 

---

알고리즘 초보가 정리한 글입니다

더 좋은 방법이나 코드에 대한 코멘트 언제나 환영합니다!