[프로그래머스] 불량 사용자

작성일: 2024-12-17

문제 링크 : https://school.programmers.co.kr/learn/courses/30/lessons/64064

접근 방식

밴 아이디에 해당 할 수 있는 아이디를 구하고, 해당 아이디로 리스트업 한 뒤에 개수를 세면 된다.

여기서 중요한 점은, 중복해서 세지 않아야 한다는 것이다. ex) {a, b} == {b, a}

잘 된 접근

• Map 자료구조를 이용해서, 밴 아이디에 해당 할 수 있는 아이디를 리스트로 구성했다.
• 밴 아이디의 조합이 ******, ******와 같이 중복되어 올 수 있기 때문에, 중복 처리를 하지 않도록 해야 한다.

결과

소스 코드

import java.util.*;

class Solution {
    static int answer = 0;
    static Set<String> set = new HashSet<>();
    static Map<String, List<String>> id;
    public int solution(String[] user_id, String[] banned_id) {
        List<String> bidList = new ArrayList<>();
        id = new LinkedHashMap<>();
        for(String bid:banned_id){
            bidList.add(bid);
            id.put(bid, new ArrayList<>());
        }
        // 모든 유저아이디를 보면서, 밴 아이디와 일치한 것이 있다면 카운트하기
        for(String bid:banned_id){
            for(String uid:user_id){
                int cnt = 0;

                // 유저아이디와 밴 아이디의 길이가 다르면 넘어가기
                if(uid.length() != bid.length()) continue;

                // 모든 문자를 비교하며 일치할 수 있는지 확인
                for(int j=0; j<uid.length(); j++){
                    if(uid.charAt(j) == bid.charAt(j) || bid.charAt(j)=='*') cnt++;
                }

                // 일치하면서 아이디를 보유하고 있지 않다면
                if(cnt==bid.length() && !id.get(bid).contains(uid)){
                    List<String> tmp = id.get(bid);
                    tmp.add(uid);
                    id.put(bid, tmp);
                }
            }
        }

        // 조합 생성
        listUp(0, new ArrayList<>(), bidList);

        return set.size();
    }

    void listUp(int i, List<String> list, List<String> bidList){
        // 모든 조합을 완성
        if(i == bidList.size()){
            // 중복 처리를 하지 않기 위해, 정렬 => 문자열로 변환하여 Set에 저장
            Collections.sort(list);
            set.add(list.toString());
            return;
        }

        // 밴 리스트에 있는, 조합 가능한 아이디 리스트를 불러옴
        for(String user:id.get(bidList.get(i))){
            // 현재 해당 아이디가 등록되어 있다면, 중복 등록 X
            if(list.contains(user)) continue;
            list.add(user);
            listUp(i+1, list, bidList);
            list.remove(user);
        }
    }
}

느낀 점

조합을 하는 과정이 머릿 속에서는 생각이 났지만, 코드화시키는 작업이 매우 어려웠다.

머릿속으로는, 밴 리스트를 작성하면서, 가능한 아이디를 하나 가져오면서, 만약 현재 전체 리스트에서 가지고 있다면 다른 아이디를 선택하여 최종 리스트를 만들 수 있다는 생각을 했다.

이 과정에서 dfs를 이용해서, 인덱스 값을 관리할 수 있다는 접근이 잘 생각이 나지 않았고 GPT에게 힌트(dfs)를 얻어서 문제를 풀 수 있었다.