[프로그래머스,java] Level3: 불량 사용자

 

문제분석

 

문제목표: 불량 사용자 리스트를 확인하여 해당 사용자와 일치하는 경우의수를 구해주세요.

 

문제를 읽어보고 프로그램관점으로 한번 생각해보니  완전탐색 문제임을 파악했다.

 

DFS문제임을 알았다면 괜찮지만,

 

문제는 이 부분이다.

 

• 제재 아이디 목록들을 구했을 때 아이디들이 나열된 순서와 관계없이 아이디 목록의 내용이 동일하다면 같은 것으로 처리하여 하나로 세면 됩니다.

 

완전탐색으로 검색된 여러결과들중 순서가 뒤죽박죽인 결과가 만약 내용물이 같으면  제거해야한다.

 

여기서 좀 많이 고민을 했지만, 아이디어를 하나 생각을해냈다.

 

visited[] 배열을 이용하여  하나의 체크문자열을 만드는것이다.

 

예를들어,  유저가 5명 불량 리스트가 3명이라면 

visited[]가 true면  O ,  false면 X를 넣는다.

 

이렇게되면 결과값으로 "OXOOX"  , "OOOXX" ... 를 통해  

HashSet에 집어넣으면 중복검사가 가능하겟거니 생각했다!

 

 

문제풀이

 

 

메인 함수부분

 

visited는 백트래킹을 사용하기 위함이지만,  이 문제에서는 추가로 중복검사용 문자열 생성으로도 사용할것이다.

 

Set<>은 중복검사용으로 생성해줬다.

 

 

DFS로직이다.  

 

for문으로 작성된 백트래킹은  전형적인 로직이다.

 

여기서 isBan() 메소드를 자세히보겠다.

 

해당 유저가 ban유저인지를 확인하는 메소드다.

 

1차로 문자열의 길이가 같은지,

2차로 문자열의 각문자가 *이거나 같은지 를확인한다.

 

 

그다음 탈출조건인 check() 메소드를 보겠다.

 

중복검사를 위한 문자열을 생성하는 메소드다. 

visited의 boolean값에따라 문자열을 집어넣는다.

 

아무 문자열이나 딱히 상관없으니.. 아무거나넣자

 

문자열을 만들었다면 Set에 넣어둔다.  HashSet은 중복컨텐츠를 알아서 걸러줄것이다.

 

 

전체코드:

import java.util.*;
class Solution {
    
boolean[] visited;
Set<String> set = new HashSet<>();
    
    public int solution(String[] user_id, String[] banned_id) {
 
        visited= new boolean[user_id.length];
        
        dfs(user_id,banned_id,0,0);
        
        return set.size();
    }
    
    public void dfs(String[] user_id, String[] banned_id,int level,int idx){
        
        if(level==banned_id.length){
            set.add(check(visited));
            return;
        }  
            for(int j=0; j<user_id.length;j++){            
                if(isBan(user_id[j],banned_id[idx])&&!visited[j]){
                    visited[j]=true;
                    dfs(user_id,banned_id,level+1,idx+1);
                    visited[j]=false;
                }
            }
        
    }
    
    public boolean isBan(String user ,String ban){
       if(user.length()!=ban.length()){
           return false;
       }
        else{
            for(int i=0;i<user.length();i++){
                if(ban.charAt(i)=='*'||user.charAt(i)==ban.charAt(i)){
                    continue;
                }
                else{
                    return false;
                }
            }
        }
        
        return true;
    }
 
    public String check(boolean[] visited){
        
       char[] arr= new char[visited.length];
        for(int i=0; i<arr.length;i++){
            if(visited[i]){
                arr[i]='O';
            }
        }
        return String.valueOf(arr);
    }
    
  
}