[카카오 기출 문제]불량 사용자- 레벨 3, 해쉬 + 이중해쉬 + 순열 + 조합

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

프로그래머스

 

이 문제같은경우 이중 HashSet을 사용하여 중복되는 제재아이디들을 제거했습니다.

문제에서 HashSet<String> 을 사용하여 "frodo", "abc123", 이렇게 직접 아이디를 넣었는데,

이렇게하지않고 bitmasking을 사용하는것이 가장 빠른 속도를 나타낼 것 같습니다.

인덱스(0,1,2,3) 이렇게 진행하는것도 가능합니다.

 

 

기억해야할점들입니다.

 

첫번째, 이중 HashSet (Double HashSet) 을 사용해도 똑같이 중복제거가 가능합니다.

- HashSet을 이중으로 이렇게 사용하여도 HashSet값을 중복체크하여 걸러내어 쉽게 사용할 수 있습니다.

HashSet<HashSet<String>> hashset = new HashSet<>();

 

두번째, 조합, 순열 구하는 알고리즘을 기억합니다.

항상 조합구하는 공식에서 종료지점에 return ; 으로 종료를 해줘야합니다. 그렇지 않으면 아래까지 내려가 indexoutofbound 에러가 뜹니다.

if(r == 0){
    HashSet<String> hashsettemp = new HashSet<String>();
    int cnt = 0;
    for(int i=0;i<User_id.length;i++){
        if(visited[i] == true){
            hashsettemp.add(User_id[i]);
        }
    }
    hashset.add(hashsettemp);
    return ;
}else{

 

 

코드입니다.

import java.util.Map.*;
import java.util.*;
class Solution {
    HashSet<HashSet<String>> hashset = new HashSet<>();
    boolean[] visited;
    String[] User_id;
    String[] Banned_id;
    int answer = 0;
    public int solution(String[] user_id, String[] banned_id) {
        User_id = user_id;
        Banned_id = banned_id;
        visited = new boolean[user_id.length];
        
        getCombination(0, 0, banned_id.length);           
        
        Iterator iter = hashset.iterator();
        return hashset.size();
    }
    
    public void getCombination(int start, int banned_id_index, int r){
        
        if(r == 0){
            HashSet<String> hashsettemp = new HashSet<String>();
            int cnt = 0;
            for(int i=0;i<User_id.length;i++){
                if(visited[i] == true){
                    hashsettemp.add(User_id[i]);
                }
            }
            hashset.add(hashsettemp);
            return ;
        }else{
            
            for(int i=0; i<User_id.length;i++){
                if(visited[i] == true)
                    continue;
 
                if(checkword(User_id[i], Banned_id[banned_id_index])){
                    visited[i] = true;
                    getCombination(start, banned_id_index+1, r-1);
                    visited[i] = false;                    
                }
            }
            
        }
        
    }
    
    public boolean checkword(String user_id, String banned_id){
        if(banned_id.length() != user_id.length()){
            return false;
        }
        for(int i=0;i<banned_id.length();i++){
            if(banned_id.charAt(i) == '*')
                continue;
            else{
                if(banned_id.charAt(i) == user_id.charAt(i)){
                    
                }else{
                    return false;
                }
            }
        }
        return true;
        
    }
}