[Programmers] 불량 사용자

문제

 

2019 카카오 개발자 겨울 인턴십 > 불량 사용자

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

 

 

아이디어

 

이번 문제의 아이디어는 순열과 조합입니다.

 

제가 생각해낸 방법은 다음과 같습니다.

 

1. user_id에서 banned_id의 길이 만큼에 해당하는 원소를 뽑아내는 조합 구하기

2. 만들어진 조합을 가지고 순열 구하기

3. 만들어진 순열을 가지고 제재 아이디가 될 수 있는지를 확인

4. 만약 제재 아이디가 되었다는 것을 확인하면 순열 구하기 중단

5. 모든 조합의 경우에 대해 2~4를 반복

 

기본적인 원리는 조합을 구하고 조합마다 순열을 구하며 user_id[index]에 있는 원소가 banned_id[index]에 있는 원소의 조건에 해당하는지를 확인하는 것입니다.

 

그리고 4번에서 제재 아이디임을 확인하면 순열 구하는 것을 중단하는 이유는 문제의 2번 예제로 설명을 드리겠습니다.

 

만약 조합으로 인해 뽑힌 user_id가 ["frodo", "crodo", "abc123"]이라고 가정하면 순열을 돌리게 될 경우 다음과 같은 경우의 수가 나옵니다.

 

1. ["frodo", "crodo", "abc123"]

2. ["frodo", "abc123", "crodo"]

3. ["crodo", "frodo", "abc123"]

4. ["crodo", "abc123", "frodo"]

5. ["abc123", "frodo", "crodo"]

6. ["abc123", "crodo", "frodo"]

 

이렇게 나오는 경우의 수들 중 동일 인덱스를 비교하며 banned_id의 규칙에 맞는 경우를 구하면 1, 3이 조건에 부합합니다.

 

하지만 ["frodo", "crodo", "abc123"]에 대한 결과값은 한 개만 나와야 되기 때문에 순열을 돌리다가 제재 아이디임을 확인하게 되면 그 즉시 순열을 모두 종료시켜주는 겁니다.

 

 

구현 코드 (Java)

 

import java.util.*;

class Solution {
	static int res; // 제재 아이디 개수
	static boolean check; // 조합에 의해 선택된 user_id들이 제재 아이디가 되었는지 확인
	
    public int solution(String[] user_id, String[] banned_id) {
        res = 0;
        String choice[] = new String[banned_id.length]; // 조합에 의해 선택되는 user_id
        makeC(user_id.length, banned_id.length, choice, user_id, banned_id);
        
        return res;
    }
    
    public static void makeC(int n, int r, String[] choice, String[] user_id, String[] banned_id) { // 조합
    	if(r <= 0) {
    		check = false; // 조합에 의해 선택된 user_id들에 대해 false로 초기화
    		makeP(0, choice, banned_id);
    		return;
    	} else if(n < r) {
    		return;
    	} else {
    		choice[r-1] = user_id[n-1];
    		makeC(n-1, r-1, choice, user_id, banned_id);
    		makeC(n-1, r, choice, user_id, banned_id);
    	}
    }
    
    public static void makeP(int n, String[] choice, String[] banned_id) { // 순열
    	if(check) { // 제재 아이디가 된 것을 확인하면 나머지 순열을 위해 생성되고 있던 재귀함수들을 모두 return
    		return;
    	}
    	
    	if(n >= choice.length) {
    		for(int i=0; i<choice.length; i++) {
    			String user = choice[i];
    			String ban = banned_id[i];
    			
    			if(user.length() == ban.length()) { // 길이가 같을 경우
    				for(int j=0; j<user.length(); j++) {
    					if(ban.charAt(j) != '*' && (user.charAt(j) != ban.charAt(j))) { // *이 아닌데 문자도 같지 않을 경우
    						return;
    					}
    				}
    			} else { // 길이가 같지 않을 경우는 제재 아이디가 될 수 없으므로 return
    				return;
    			}
    			
    			if(i == choice.length-1) { // choice된 모든 user_id들이 banned_id에 속할 경우 = 제재 아이디인것을 확인한 경우
    				res++; // 제재 아이디 개수 증가
    				check = true; // 순열을 중단하기 위해 user_id의 조합이 제재 아이디라는 것을 체크
    			}
    		}
    		
    		return;
    	}
    	
    	for(int a=n; a<choice.length; a++) {
    		String temp = choice[a];
    		choice[a] = choice[n];
    		choice[n] = temp;
    		
    		makeP(n+1, choice, banned_id);
    		
    		temp = choice[a];
    		choice[a] = choice[n];
    		choice[n] = temp;
    	}
    }
}

 

 

읽어주셔서 감사합니다.