[프로그래머스/Java] [2019 카카오개발자 겨울 인턴십] 불량 사용자

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

프로그래머스

 

 

🔍  해결 과정

DFS 및 백트래킹 과정으로 문제를 해결하였습니다. 

문제에서는 user_id, banned_id 둘 다 최대 길이가 8이기 때문에 일반 구현으로도 문제를 해결하는 방법도 있지만, 저는 제일 처음 떠올랐던 아이디가 DFS를 활용한 조합 문제였습니다. 

하지만 단순히 N개 중에서 M개를 선택하는 일반 조합 문제와는 다르게 이 문제는 banned_id에 들어 있는 필터링 이름들의 조건에 맞는 이름들을 user_id에서 찾아가면서 선택해야 하기 때문에 그에 맞는 방식으로 코드 구조를 잘 설계해야 합니다. 그래서 어떤 방식으로 설계를 했는지 그림을 통해서 설명하겠습니다.

우선 먼저 코드 과정을 코드 기준으로 간단히 설명하자면 다음과 같습니다.

1️⃣ banned_id의 특정 인덱스에 존재하는 필터링에 조건에 부합한 적절한 이름들을 리스트로 모아둡니다. 즉, 코드에서 List<Integer>[] 타입을 가진 matched 변수를 활용하여 필터링 이름 조건에 맞는 user_id의 사용자 이름을 모아둡니다. 이 때는 중복을 신경 안써도 됩니다.
2️⃣ matched에서 모은 이름들을 활용하여 DFS를 진행해 경우의 수를 구해줍니다.

 

 

문제에서 예제 3을 기준으로 설명하겠습니다.

user_id: ["frodo", "fradi", "crodo", "abc123", "frodoc"]
banned_id: ["fr*d*", "*rodo", "******", "******"]
결괏값: 3

 

 

1️⃣ 단계: banned_id의 필터링 조건에 맞는 이름들을 List<Integer>[] 타입의 matched에 담는다.

 

반복문을 활용해서 banned_id을 돌아보면서 banned_id[idx] 조건에 맞는 이름들을 하나씩 리스트로 만들면서 담아주고 결과를 그림으로 표현하면 다음과 같습니다.

matched의 결과

fr*d*

matched의 0번 인덱스에 해당하는 fr*d*의 문자열 패턴은 user_id의 0번 인덱스인 frodo과 fradi에 대응됩니다.

 

 

2️⃣ 단계: 완성한 matched에서 DFS를 적용한다.

설계 조건은 먼저 DFS를 돌 때의 Depth 기준을 matched의 인덱스 사이즈로 설정하고, 해당 depth에서 user_id인덱스 정보를 하나씩 받아오는 방식으로 설계를 하면 됩니다. 코드 부분에서 process 메서드에 해당하는 부분입니다.

 

첫 번째 재귀를 기준으로 그림 순서대로 데이터를 살펴보는 과정을 나열하겠습니다. 빨간색 표시 부분은 데이터를 살폈음을 의미합니다.

위 그림과 같은 과정을 거치면 user_id는 0번 인덱스와 2번 인덱스, 3번 인덱스, 4번 인덱스를 살피게 됩니다. 이 때 0번 인덱스와 3번 인덱스를 두 번씩 살펴보는 것은 코드의 used 배열을 활용하여 방지하였습니다.

 

그래서 첫 번째 재귀 패턴에서 ["0, 2, 3, 4"]의 내용이 만들어지는데 이 경우를 저장하기 위해서 저는 Set<String> 타입의 resultSet 자료구조를 활용하였습니다. Set을 활용한 이유는 같은 "0, 2, 3, 4"의 경우가 중복되는 것을 방지하기 위함입니다.

 

 

이렇게 모든 재귀 과정을 다 거치고 나면 resultSet에는 최종적으로 다음의 내용이 담기게 됩니다.

resultSet: ["0, 1, 3, 4", "0, 2, 3, 4", "1, 2, 3, 4"]

 

이 모든 경우들의 내용들을 resultSet이 담고 있으므로 resultSet의 size가 곧 필터가 가능한 모든 경우의 수를 의미하는 것입니다.

 

 

💬 회고점

걸린시간: 1시간 30분

 

단순한 조합 문제를 주어진 조건에 맞게 어떻게 적용할지 고민하며 해결해야 하는, 의미 있는 문제였습니다.

이와 비슷한 유형의 문제도 쉬운 난이도부터 차근차근 풀어나가야겠다는 생각을 하게 되었습니다.

 

설계 구조를 그림으로 이것저것 적극적으로 그려보면 코드를 설계하는 방식도 많이 연습해야겠다는 생각도 하게 되었습니다. 

 

---

✏️ 코드

import java.util.*;

class Solution {
    
    private int answer = 0;
    private Set<String> resultSet = new HashSet<>();
    private List<Integer>[] matched;
    private int[] arr;
    boolean[] used;
    
    public int solution(String[] user_id, String[] banned_id) {
        return getResult(user_id, banned_id);
    }
    
    private int getResult(final String[] user_id, final String[] banned_id) {
        int userCount = user_id.length;
        int banCount = banned_id.length;
        
        matched = new ArrayList[banCount];
        for (int i = 0; i < banCount; ++i) {
            matched[i] = new ArrayList<>();
            String ban = banned_id[i];
            
            for (int j = 0; j < userCount; ++j) {
                if (isValid(user_id[j], ban)) {
                    matched[i].add(j);
                }
            }
        }
        
        arr = new int[banCount];
        used = new boolean[userCount];
        
        process(user_id, banCount, 0);
        
        return resultSet.size();
    }
    
    private void process(final String[] user_id, int banCount, int idx) {
        
        if (idx >= banCount) {
            
            StringBuilder sb = new StringBuilder();
            int[] arrCopy = arr.clone();
            Arrays.sort(arrCopy); 
            
            for (int i = 0; i < banCount; ++i) {
                sb.append(arrCopy[i]).append(", ");
            }
            
            resultSet.add(sb.toString());
            return;
        }
        
        for (Integer userIdx : matched[idx]) {
            if (used[userIdx]) {
                continue;
            }
            
            used[userIdx] = true;
            arr[idx] = userIdx;
            
            process(user_id, banCount, idx + 1);
            
            arr[idx] = 0;
            used[userIdx] = false;
        }
    }
    
    private boolean isValid(final String user, final String banned_user) {
        if (user.length() != banned_user.length()) {
            return false;
        }
        
        int banLength = banned_user.length();
        
        for (int i = 0; i < banLength; ++i) {
            char bc = banned_user.charAt(i);
            char uc = user.charAt(i);
            
            if (bc == '*') {
                continue;
            }
            
            if (bc != uc)  {
                return false;
            }
        }
        
        return true;
    }
}