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

leehyunjon·2022년 4월 30일

카카오 프로그래머스

Algorithm

목록 보기

17/162

불량 사용자 : https://programmers.co.kr/learn/courses/30/lessons/64064

Problems

Solves

분명 비슷한 유형의 문제를 풀어봤는데 생각 못했던게 속상했던 문제.

백트래킹과 문자열의 matches를 이용하여 조건에 맞는 아이디 조합을 문자열로 만들어 비교하여 해결했다.

문제 풀이 순서는 아래와 같다.

문자열의 matches를 활용하기 위해 regex 하나의 char을 가리키도록 '*'을 '.'으로 변환 시킨다.
백트래킹으로 각 아이디와 비교문자열을 matches를 활용해 아이디 조합 문자열을 만들어간다.
아이디 조합 문자열을 완성시켰다면 HashSet을 이용해 중복 조합을 제거하여 저장한다.
완성된 아이디 조합의 갯수를 반환한다.

Code

import java.util.HashMap;
import java.util.HashSet;
import java.util.Arrays;
class Solution {
    HashSet<String> set;
    String[] userList;
    String[] banList;
    boolean[] visit;
    public int solution(String[] user_id, String[] banned_id) {
        set = new HashSet<>();
        visit = new boolean[user_id.length];
        
        //*문자를 .으로 치환
        for(int i=0;i<banned_id.length;i++){
            banned_id[i] = banned_id[i].replace("*",".");
        }
        userList = user_id;
        banList = banned_id;
        
        //문자열 조합 생성
        setList(0, "");
        
        return set.size();
    }
    
    //문자열 조합 생성 함수
    //idx : 비교문자열 index, id : 아이디 조합 문자열
    void setList(int idx, String id){
    	
        //아이디 조합 문자열을 완성시켰다면
        //중복 문자열을 방지하기 위해 정렬 후 hashSet에 저장
        if(idx == banList.length){
            String[] splitId = id.split(" ");
            Arrays.sort(splitId);
            
            StringBuilder sb = new StringBuilder();
            for(String i : splitId){
                sb.append(i);
            }
            set.add(sb.toString());
            return;
        }
        
        //백트래킹을 이용하여
        //사용되지 않은 아이디와 비교 문자열을 matches로 비교하여 아이디 조합을 생성해나간다.
        for(int i=0;i<userList.length;i++){
            if(userList[i].matches(banList[idx]) && !visit[i]){
                visit[i] = true;
                setList(idx+1, id+ " "+userList[i]);
                visit[i] = false;
            }
        }
    }
}