2019 카카오 개발자 겨울 인턴십(불량 사용자) - Java

[불량 사용자]

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

프로그래머스

 

* 로직

• 응모자 아이디를 불량 사용자 아이디 개수만큼 뽑는 경우의 수를 구한다(순열)
• 경우의 수가 뽑힌 상태에서, 뽑힌 아이디와 불량 아이디를 비교한다 (불량 아이디의 index만큼 포문 진행)
  • 만약, 뽑힌 아이디와 불량 아이디의 글자 수가 다르다면 false
  • 글자 수가 같다면 한 글자씩 비교한다
    • *을 만나면 continue
    • 서로 글자가 다르다면 false
• 뽑힌 아이디와 불량 아이디를 비교한 결과가 true라면 해당 경우의 수를 오름차순 정렬 후 HashSet에 삽입한다
  (순열을 구하기 때문에 중복되는 경우를 방지하고자 HashSet을 사용했고, HashSet의 중복처리를 위해 오름차순 정렬 후에 삽입을 진행했다)
  
  
• HashSet의 사이즈를 답으로 출력한다

 

import java.util.Collections;
import java.util.HashSet;
import java.util.LinkedList;

class Solution {
    static int N;
    static int R;
    static boolean[] checked;
    static HashSet<LinkedList<String>> hashSet;
    
    public int solution(String[] user_id, String[] banned_id) {
        int answer = 0;
        N = user_id.length;
        hashSet = new HashSet<>();

        checked = new boolean[N];
        R = banned_id.length;
        LinkedList<String> path = new LinkedList<>();
        doProcess(user_id, banned_id, R, path);

        answer = hashSet.size();
        return answer;
    }
    
    private static void doProcess(String[] user_id, String[] banned_id, int r, LinkedList<String> path) {
        if(r == 0) {
            if(isCorrect(user_id, banned_id, path)) {
                LinkedList<String> tmp = new LinkedList<>();
                for(int i=0; i<path.size(); ++i) {
                    tmp.add(path.get(i));
                }

                Collections.sort(tmp);
                hashSet.add(tmp);
            }
            return;
        }

        for(int i=0; i<N; ++i) {
            if(!checked[i]) {
                checked[i] = true;
                path.add(user_id[i]);
                doProcess(user_id, banned_id, r-1, path);
                path.removeLast();
                checked[i] = false;
            }
        }
    }

    private static boolean isCorrect(String[] user_id, String[] banned_id, LinkedList<String> path) {
        for(int i=0; i<R; ++i) {
            String userId = path.get(i);
            String bannedId = banned_id[i];

            // 글자 수가 다르다면 false
            if(userId.length() != bannedId.length()) return false;

            // 글자 수는 같다면 비교
            else {

                // 한글자씩 비교하면서 *을 만나면 계속 진행
                for(int s=0; s<userId.length(); ++s) {
                    String word_user = userId.substring(s, s+1);
                    String word_banned = bannedId.substring(s, s+1);

                    // 제재 글자가 *이라면 continue
                    if(word_banned.equals("*")) continue;

                    // 서로 글자가 다르면 false
                    if(!word_user.equals(word_banned)) {
                        return false;
                    }
                }
            }
        }

        return true;
    }
}

 

경우의 수의 중복을 방지하기 위해 오름차순 정렬 후 HashSet에 넣는 방법 말고도 더 유용한 방법이 있다는 것을 알게되었다. 바로 '비트 마스크'다. (a,b)를 뽑든 (b,a)를 뽑든 비트 마스크는 같아지기 때문에 hashSet에 해당 비트 마스크 값을 넣어주면 중복은 자동적으로 처리된다. 아래 링크를 통해 참고해보는 것도 좋을거 같다.

 

https://wonillism.tistory.com/10?category=864853

[2019 kakao winter internship] 03. 불량 사용자 (cpp/python)