프로그래머스 (불량 사용자 Level 3) - java

문제

개발팀 내에서 이벤트 개발을 담당하고 있는 "무지"는 최근 진행된 카카오이모티콘 이벤트에 비정상적인 방법으로 당첨을 시도한 응모자들을 발견하였습니다. 이런 응모자들을 따로 모아 불량 사용자라는 이름으로 목록을 만들어서 당첨 처리 시 제외하도록 이벤트 당첨자 담당자인 "프로도" 에게 전달하려고 합니다. 이 때 개인정보 보호을 위해 사용자 아이디 중 일부 문자를 '*' 문자로 가려서 전달했습니다. 가리고자 하는 문자 하나에 '*' 문자 하나를 사용하였고 아이디 당 최소 하나 이상의 '*' 문자를 사용하였습니다.
"무지"와 "프로도"는 불량 사용자 목록에 매핑된 응모자 아이디를 제재 아이디 라고 부르기로 하였습니다.

이벤트 응모자 아이디 목록이 담긴 배열 user_id와 불량 사용자 아이디 목록이 담긴 배열 banned_id가 매개변수로 주어질 때, 당첨에서 제외되어야 할 제재 아이디 목록은 몇가지 경우의 수가 가능한 지 return 하도록 solution 함수를 완성해주세요.

 

유형 : 조합 + 문자열

 

접근 방식

• 카카오 코테 문제이다. 보기엔 단순한 조합 문제인거 같은데 역시 카카오는 카카오다. 생각보다 까다로운 문제이다.
• 내가 만든 메서드를 우선 설명하겠다.
  • comb() 주어진 user_id 배열을 n이라 놓고 banned_id를 r이라 하겠다. 즉 사용자 n명 중에서 r명을 추출하는 메서드이다.
  • n명 중 r명을 추출했다면 go() 메서드를 수행할 것이다.
  • go() 메서드는 추출한 r명으로 banned_id를 구성할 수 있는지 판단하는 메서드이다.
    • 난 이부분을 재귀로 구성하여 1번의 조합을 만들 수 있다면 isR 변수를 true로 설정하고 result를 1 증가하도록 구성했다.
  • 다른 사람의 풀이를 보니 한번의 재귀만으로 해당 문제를 해결할 수 있다는 것을 알았다.
  • 참고 : https://velog.io/@js4183/%ED%94%84%EB%A1%9C%EA%B7%B8%EB%9E%98%EB%A8%B8%EC%8A%A4-%EC%BD%94%ED%85%8C-%EB%B6%88%EB%9F%89-%EC%82%AC%EC%9A%A9%EC%9E%90.java

 

전체 코드

class Solution {
    static int result = 0;
    static boolean[] v;
    static boolean[] tmpV;
    static int n;
    static int r;
    static boolean isR;
    static String[] u;
    static String[] b;
    
    public int solution(String[] user_id, String[] banned_id) {
        int answer = 0;
        
        u = user_id;
        b = banned_id;
        
        n = user_id.length;
        r = banned_id.length;
        
        v = new boolean[n];
        tmpV = new boolean[r];
        
        comb(0,0);
        
        answer = result;
 
        return answer;
    }
    
    static void print() {
        for(int i = 0 ; i < n ; i++) {
            if(v[i])
                System.out.print(i+" ");
        }System.out.println();
    }
    
    
    static void go(int idx) {
        
        if(isR)
            return;
        
        if(idx == n) {
            isR = true;
            return;
        }
        
        if(!v[idx])
            go(idx + 1);        
        
        else {
            for(int i = 0 ; i < r ; i++) {
                if(!tmpV[i] && can(u[idx],b[i])) {
                    tmpV[i] = true;
                    go(idx + 1);
                    tmpV[i] = false;
                }
            }
        }
    }
    
    
    static boolean can(String f, String s) {
        
        if(f.length() != s.length())
            return false;
        
        char[] farr = f.toCharArray();
        char[] sarr = s.toCharArray();
        
        for(int i = 0 , size = farr.length ; i < size ; i++) {
            if(sarr[i] == '*')
               continue;
            
            if(farr[i] != sarr[i])
                return false;
        }
        
        
        return true;
    }
    
    static void comb(int idx,int num) {
       if(num == r) {
           isR = false;
           go(0);
           
           if(isR)
               result+= 1;
           
           return;
       }
       
        for(int i = idx ; i < n ; i++) {
            if(!v[i]) {
                v[i] = true;
                comb(i + 1,num + 1);
                v[i] = false;
            }
        }
    }
}