Algorithm
6 Aug 2020

2019 카카오 겨울 인턴 불량 사용자 [Java]

2019 카카오 겨울 인턴 튜플 [Java]


문제의도

  • dfs를 활용할줄 아는가?


문제 풀이 방법(2가지)

  1. dfs를 활용하여 baned항목을 추출한뒤 set자료구조로 중복 구분

  2. 비트연산을 이용하여 푸는 방법(<- 추후 풀이 추가 예정)

import java.util.*;
class Solution {
    Boolean[] used=new Boolean[8];

    //순서에 관계 없이 내용이 동일 하면 같은 것을 처리하기 위해 set자료구조 활용
    Set<String> set=new HashSet<>();

    //user와 baned id 검사
    public boolean check(String user,String banned){
        if(user.length()!=banned.length())return false;
        for(int i=0;i<user.length();i++){
            if(user.charAt(i)!=banned.charAt(i)&&banned.charAt(i)!='*'){
                return false;
            }
        }
        return true;
    }
    public void dfs(String[] user_id, String[] banned_id,int banIdx){
        if(banIdx==banned_id.length){
            String users="";
            for(int i=0;i<user_id.length;i++){
                if(used[i]){
                    users+=user_id[i];  
                }
            }
            set.add(users);
            return;
        }
        for(int i=0;i<user_id.length;i++){
            if(!used[i]&&check(user_id[i],banned_id[banIdx])){
                used[i]=true;
                dfs(user_id,banned_id,banIdx+1);
                used[i]=false;
            }
        }
    }
    public void init(){
        for(int i=0;i<8;i++){
            used[i]=false;
        }
    }
    public int solution(String[] user_id, String[] banned_id) { 
        init();
        dfs(user_id,banned_id,0);
        return set.size();
    }
}
Tags:
0 comments