[프로그래머스]불량사용자

programmers.co.kr/learn/courses/30/lessons/64064

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

 

나의 풀이

1. 먼저 불량사용자에 해당하는 사용자를 찾아 arrayList<set> bannedList 형태로 만든다.

2. 불량사용자 순열을 만든다.

3. 이전에 만든 bannedList의 순서에 있는지 확인 후 resutlSet에 만든다.

4. 순열이기 때문에 겹칠 수 있어서 resultSet을 이용하여 중복을 제거한다.

package com.example.demo;

import java.util.*;
class Solution {
	static int banUser;
	static ArrayList<Set> arrList;
	static Set<Set> resultSet;
	static boolean[] visit;
	static String[] result;
	static Set<Set<String>> set;
	public int solution(String[] user_id, String[] banned_id) {
        int answer = 0;
        banUser = banned_id.length;
        
        visit = new boolean[user_id.length];
        result = new String[banUser];
        arrList = new ArrayList<Set>();
        resultSet = new HashSet<>();
        
        //불량 사용자에 해당하는 사람들 목록 만들기.
        for (int i = 0; i < banUser; i++) {
        	String bannedPattern = banned_id[i];
        	Set<String> tempSet = new HashSet<String>();
        	for (String user : user_id) {
        		boolean isRight = true;
				if(user.length() != bannedPattern.length()) continue;
				for (int j = 0; j < bannedPattern.length(); j++) {
					char bannedC = bannedPattern.charAt(j);
					char userC = user.charAt(j);			
					if(bannedC == '*') continue;
					if(userC != bannedC) {
						isRight = false;
						break;
					}
					
				}
				if(isRight) tempSet.add(user);
			}
        	arrList.add(tempSet);
		}
        
        dfs(user_id, 0,0);
        answer = resultSet.size();
        return answer;
    }
    public static void dfs(String[] user_id, int length, int startCnt) {
    	
    	if(length == banUser) {
    		Set<String> tempSet = new HashSet<String>();
    		for (int i = 0; i < length; i++) {
				String target = result[i];
				tempSet.add(target);
				//검증하기. 만든 사용자 리스트에서 1번째 사람은 ban리스트 1번쨰 안에 들어가야함.
				if(!arrList.get(i).contains(target)) return;
			}

    		//중복방지를 위해 set에 넣기.
    		resultSet.add(tempSet);
    		return;
    	}
    	
    	//일정 인원별 사용자 묶음 만들기
    	for (int i = 0; i < user_id.length; i++) {
    		if(visit[i]) continue;
    		visit[i] = true;
    		result[length] = user_id[i];
    		dfs(user_id,length+1, i+1);
    		visit[i] = false;
		}
    	
    }
}

정규식이 서투르고 문제의 해결 방식에 대해 갈피를 잘 못 잡아서 오래 걸린 문제.

구현력이 부족함도 느꼈다.

1. 정규식 -> if문으로 처리 => 괜찮음

2.  문제 해결 방식 -> 조합으로 풀면 되는 줄 알았지만 순열이었고, 순열로 풀이 시 중복될 법한 건에 대해 처리를 잘 해줘야했다. Set<Set>

3. set을 써야함은 알았는데 어디에 써야했는지를 잘 몰랐다. ->  dfs시 visit대신 써도 되지만 검증하는 부분에서 사용함.