[Java] 프로그래머스 - 불량 사용자 (3단계)

코딩 테스트 풀이 체크리스트
2시간 내에 풀었는가?	X
본인의 실력으로 풀었는가?	O

 

코딩테스트 연습 - 불량 사용자

 

 

 

 

 

import java.util.*;
class Solution {
    HashMap<String, ArrayList<String>> map;
    ArrayList<String> answer;
    public int solution(String[] user_id, String[] banned_id) {
        map = new HashMap<>(); //banned_id에 해당하는 user_id 검출용
        answer = new ArrayList<>(); //만들 수 있는 banned 리스트 제작용
        
        for (int i = 0; i < banned_id.length; i++) {
        	ArrayList<String> list = map.getOrDefault(banned_id[i], new ArrayList<>());
			//만약 map에서 가져온 배열의 길이가 0이 아니면 이미 체크한 banned_id이기 때문에 continue;            
            if (list.size() != 0) continue;
            
            //user_id와 banned_id[i]를 각각 비교하여 불량 사용자에 해당하는지 파악
            for (int j = 0; j < user_id.length; j++) {
                if (banned_id[i].length() == user_id[j].length()) {
                    boolean value = checkWord(user_id[j], banned_id[i]);
                    if (value) list.add(user_id[j]);
                }
            }
            
            map.put(banned_id[i], list);
        }
        
        create(banned_id, 0, new ArrayList<>());
        return answer.size();
    }
    
    public void create(String[] key, int index, ArrayList<String> result) {
        if (key.length == index) {
           	//이미 만든 리스트인지 확인하기 위해 오름차순 정렬 후 String화해서 확인하기
            Collections.sort(result);
            String word = Arrays.toString(result.toArray());
            if (answer.indexOf(word) == -1) answer.add(word);
            return;
        }
        
        ArrayList<String> value = map.get(key[index]);
        for (int i = 0; i < value.size(); i++) {
            String word = value.get(i);
            if (result.indexOf(word) != -1) continue;
            
            ArrayList<String> temp = new ArrayList<>();
            temp.addAll(result);
            temp.add(word);
            
            create(key, index+1, temp);
        }
    }
    
    public boolean checkWord(String a, String b) {
    	//String배열로 비교하면 시간복잡도가 올라가기 때문에 char배열로 비교
        char[] alist = a.toCharArray();
        char[] blist = b.toCharArray();
        
        for (int i = 0; i < alist.length; i++) {
            if (blist[i] != '*' && alist[i] != blist[i]) {
                return false;
            }
        }
        
        return true;
    }
}

 

테스트 1 〉	통과 (0.28ms, 73.4MB)
테스트 2 〉	통과 (0.37ms, 76.7MB)
테스트 3 〉	통과 (0.59ms, 76.4MB)
테스트 4 〉	통과 (0.33ms, 76MB)
테스트 5 〉	통과 (101.17ms, 115MB)
테스트 6 〉	통과 (4.97ms, 75.4MB)
테스트 7 〉	통과 (0.38ms, 75.6MB)
테스트 8 〉	통과 (0.38ms, 74.3MB)
테스트 9 〉	통과 (0.44ms, 71.1MB)
테스트 10 〉	통과 (0.29ms, 74.2MB)
테스트 11 〉	통과 (0.68ms, 73.5MB)