2019 카카오 겨울 개발자 인턴십 코딩테스트 - 불량 사용자(feat.Java)

문제 정보는 아래 링크 확인 부탁드립니다!

 

[불량 사용자]

프로그래머스

 

문제 접근 방법

- 불량 사용자 배열을 정규 표현식으로 변환

- DFS를 순환

  - 문제 정보는 아래 링크 확인 부탁드립니다!

 

 

 

[불량 사용자]

 

프로그래머스

 

코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요.

 

programmers.co.kr

 

 

문제 접근 방법

 

- 불량 사용자 배열을 정규 표현식으로 변환

 

- DFS를 순환(불량 사용자 인덱스, 일치하는 응모자 ID's)

  - 응모자 배열과 현재 불량 사용자의 아이디가 일치하면

  - DFS의 파라미터에 다음 불량 사용자 인덱스와 일치하는 응모자 ID를 넣고 순환

 

- 불량 사용자 인덱스가 불량 사용자 배열의 사이즈와 일치하면(DFS를 다 순환했으면)

  - 무작위로 석여있는 응모자 ID's의 순서를 맞춰주고,

  - HashSet에 해당 문자열 순서가 들어있지 않다면, 추가해준다.

 

- DFS를 다 순환했다면

  - 결과 변수에 HashSet의 사이즈를 담고 리턴해준다.

 

[소스코드]

import java.util.*;

class Solution {
    private int user_len,ban_len;
    private String[] user_id,banned_id;
    private boolean[] visited;//응모자 ID의 방문 여부
    private HashSet<String> set;//불량 사용자 목록 세트
    
    public int solution(String[] User_id, String[] Banned_id) {
        
        user_id = User_id;
        banned_id = Banned_id;
        
        user_len = user_id.length;
        ban_len = banned_id.length;
        
        visited = new boolean[user_id.length];
        
        set = new HashSet<>();
        
        int answer = 0;
        
        dfs(0,"");//DFS 순환 탐색을 통해서 결과값을 HashSet에 저장
        
        answer = set.size();
            
        return answer;
    }
    
    public void dfs(int idx, String str) {//idx는 현재 불량 사용자 배열 인덱스,  
                                          //str은 일치하는 불량 사용자 목록
        
        if (idx == ban_len) {//불량 사용자 배열의 현재 인덱스가 배열의 사이즈와 같을 때
                             //즉, DFS의 순환이 마지막일 때,
            
            StringBuilder sb = new StringBuilder("");//문자열을 추가하기 때문에 String보다 적합
            
            for (int i = 0; i < user_len; i++) {//응모자 아이디가 목록에 포함되어있다면 sb에 추가
                                                //값을 순서대로 정렬해주기 위함!
                
                if (str.contains(""+i)) sb.append(""+i);
            }
            
            if (!set.contains(sb.toString())) {//정렬된 목록이 HashSet에 포함되어있지 않다면,
                                               //set에 추가시켜준다.
                 //System.out.println(str);
                set.add(sb.toString());
            }
            
            return;
        }
        
        for (int i = 0; i < user_len; i++) {//응모자 아이디 중에서 현재 불량 사용자와 일치하는 값을 찾는다.
            
            if (visited[i]) continue;//이미 목록에 들어있는 값이면 패스한다.
            
            String regex = banned_id[idx].replace("*",".");//정규식 체크 fr*d* -> fr.d.
                
                if (user_id[i].matches(regex)) {//정규식과 일치한다면,
                                                //해당 응모자의 방문 여부를 바꿔주고 DFS 탐색을 한다.
                    
                    visited[i] = true;
                    dfs(idx+1,str+i);
                    visited[i] = false;
                }
        }
        
    }
}

 

[정확성 테스트]

 

 

ps. 해당 문제를 비트 마스킹으로 접근하는 방법도 있다. 비트 마스킹으로 접근할 경우 속도가 더 빠르고 코드도 간결해질 수 있기 때문에 해보는 것도 좋을 것 같다.