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

프로그래머스 불량 사용자 문제는 사용자 리스트와 밴 리스트가 주어졌을 때 밴된 사용자를 구하는 문제다. 난이도는 레벨3이며 그래프 탐색을 통해 해결할 수 있다.

 

프로그래머스 - 불량 사용자 문제 정보

알고리즘 분류

- 그래프

난이도

- Level 3

 

문제 요약

• 사용자 아이디 리스트와 밴 아이디 리스트가 주어짐
• 밴 아이디 리스트는 사용자 아이디 중 밴된 사용자들의 아이디로, 아이디의 일부가 *로 마스킹처리 되어있음
• 밴된 사용자 리스트의 경우의 수를 구하라.

 

문제 풀이 과정

• 쉬운 문제인 줄 알고 시작했으나.. 생각보다 오래 걸림
• 일단 사용자 아이디 각각이 어떤 밴 아이디에 걸리는지를 확인해서 따로 저장함
• 그리고 밴 아이디 개수만큼 사용자 아이디를 뽑아야 되는데, 문제는 순서가 없고 중복도 안된다는 것..!
• 대신 사용자 아이디 리스트의 길이가 최대 8이라서, 8자리 String을 Set에 넣어서 답 중복 확인함

코드

import java.util.*;

class Solution {
    
    private boolean[][] candidates = new boolean[8][8];
    private Set<String> answers = new HashSet<>();
    private int userLen = 0, banLen = 0;
    
    public int solution(String[] user_id, String[] banned_id) {
        userLen = user_id.length;
        banLen = banned_id.length;
        
        // candidates 배열에 i번째 밴아이디에 j번째 사용자 아이디가 밴되는지 체크
        for(int i = 0; i < banLen; i++) {
            for(int j = 0; j < userLen; j++) {
                if (isBanned(banned_id[i], user_id[j])) {
                    candidates[i][j] = true;
                }
            }
        }
        
        // 매핑되는 경우의 수를 8자리 String으로 표현하여 구함
        getCases(new StringBuilder("00000000"), 0);
        
        return answers.size();
    }
    
    // banned_id에 user_id가 해당되는지 확인
    private boolean isBanned(String banned_id, String user_id) {
        if (banned_id.length() == user_id.length()) {
            for(int idx = 0; idx < banned_id.length(); idx++) {
                if (banned_id.charAt(idx) != '*'
                   && banned_id.charAt(idx) != user_id.charAt(idx)) {
                    return false;
                }
            }
            return true;
        }
        return false;
    }
    
    // visited: 현재까지 밴된 아이디들, hereBanIdx: 이번에 확인할 밴아이디
    private void getCases(StringBuilder visited, int hereBanIdx) {
        // 마지막 밴아이디까지 체크했으면 정답셋에 넣기
        if (hereBanIdx == banLen) {
            answers.add(visited.toString());
            return;
        }
        // 다음 밴아이디로 밴되는 사용자아이디 확인 후 방문
        for(int idx=0;idx<userLen;idx++) {
            if (candidates[hereBanIdx][idx] && visited.charAt(idx) == '0') {
                visited.replace(idx,idx+1,"1");
                getCases(visited, hereBanIdx+1);
                visited.replace(idx,idx+1,"0");
            }
        }
    }
}

• 시간복잡도: O(N*N)
• 공간복잡도: O(N*N)

개선사항

• 애초에 DFS를 의도한 문제라서 N이 매우 작지만, 비슷한 경우에서 N이 조금이라도 커지면 더 나은 방법을 찾아야 할 것 같다.
• String으로 비트마스크를 표현하지 말고 진짜 비트마스크를 써보는 시도를 해보자.