[코딩테스트] 프로그래머스 - 불량 사용자(Java, Level3)

안녕하세요~

제일 열심히 해야될 주말에 설렁설렁 공부하는둥 마는둥하다가

이제서야 이문제를 풀었네요... 사실 푼거라고도 말하기 창피한게 결국 아이디어는 다른 분들이 올린 힌트를 보고 풀었습니다.

 

그럼에도 풀었다는데 의의를 두고 문제 만나보시죠!

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

프로그래머스

 

다음은 제가 작성한 코드입니다.

 

import java.util.*;

class Solution {
    
    Map<Integer, String> depth;
    Set<Set<String>> set;
    int answer=0;
    String last_key="";
    
    public int solution(String[] user_id, String[] banned_id) {
        //int answer = 0;
        Map<String, Boolean>visited=new HashMap<>();
        depth=new HashMap<>();
        set=new HashSet<>();
        Set<String> temp_set=new HashSet<>();
        
        for(String user_id_ele:user_id)
            visited.put(user_id_ele,false);
        
        int number=0;
        for(String banned_id_ele : banned_id)
        {
            depth.put(number,banned_id_ele);
            number++;
        }
        
        dfs(visited,0,temp_set);
        answer=set.size();
        return answer;
    }
    public void dfs(Map<String, Boolean>visited,int index,Set<String>temp_set)
    {
        //System.out.println(index);
        if(index==depth.size())
        {
            set.add(new HashSet<>(temp_set));
            return;
        }
            
        
        String banned_id_ele=depth.get(index);
        for(String key:visited.keySet())
        {
            if(key.length()==banned_id_ele.length())
            {
                if(!visited.get(key))
                {
                    boolean checker=true;
                    for(int i=0;i<key.length();i++)
                    {
                        // *인부분컨티뉴처리
                        if(banned_id_ele.charAt(i)=='*')
                            continue;
                        // 하나씩비교
                        if(key.charAt(i)!=banned_id_ele.charAt(i))
                        {
                            checker=false;
                            break;
                        }
                    }
                    if(checker==true)
                    {
                        if(!temp_set.contains(key))
                        {
                            temp_set.add(key);
                            dfs(visited,index+1,temp_set);
                            temp_set.remove(key);
                        }
                        /*System.out.println(index+" : "+key);
                        visited.replace(key,true);
                        last_key=key;
                        //index=index+1;
                        dfs(visited,index+1);
                        visited.replace(key,false);*/
                    }
                }  
                
            }
        }
    }
    
    
}

주말 내내 고민한 코드 치고는 코드가 꽤길고 지저분하게 나왔습니다. ㅠㅠ

여전히 제가 알고리즘짜는데 부족하다는 뜻이겠죠?

 

간단한 문제에 대한 생각을 달아보자면

이 문제의 핵심은 바로 dfs! 입니다.

또한 여기에서 중복을 제거! 라는 두가지의 핵심 개념이 있네요.

 

저는 hash set의 요소가 hashset이어도 중복을 찾아낸다는 사실이 신기했습니다.

dfs 다짜놓고 사실 중복요소인줄도 모르고... ㅠㅠㅠ 헤맸습니다.

 

여기서 추가적으로 간단하게 만들 수 있는 사항을 꼽자면

① banned_id array를 저는 다시 hashset인 depth로 다시 만들어 사용했는데 index를 갖고사용하기에 바로 banned_id array를 사용하면 될것 같습니다.

② 다음은 hashmap인 visited입니다. dfs라길래 호다닥 visited부터 만들었는데 이부분을 hashset<hashset>의 구조인 set변수로 대체했습니다. 그럼에도 남겨놓은 이유는 탐색시 이미 visited인건 바로넘어가게 하기위해 남겨뒀습니다.

 

이렇게 두 개의 부분을 줄인다면 더욱 빠른 탐색이 가능할것 같습니다.

또한 해당 문제의 Test case중 3번이 오류가 날 수 있습니다.

 

이것도 찾아보니 

        /*if(index==depth.size())
        {
            set.add(temp_set);
            return;
        }*/
 
 		if(index==depth.size())
        {
            set.add(new HashSet<>(temp_set));
            return;
        }

기존에는 윗 주석처리된 코드처럼 사용했다가 밑 코드처럼 사용하니 맞았습니다.

해당부분도 찾아봐야겠습니다.

신기하네요~

 

네... 오늘 문제는 여기까지 입니다. 사실 출근길에 폰으로 낑낑거리면서 푸느라 오늘은 SQL문제도 못봤네요~

 

오늘은 여기까지 안녀엉~:D