HashSet 과 백트래킹 이용하기

프로그래머스 2019 카카오 인턴십 Level 3 문제인 불량 사용자를 Java로 풀어보았다.
HashSet 자료구조를 사용했고 백트래킹으로 쉽게(?) 해결이 가능했던 문제다. 이걸 떠올리는 게 쉽지는 않았지만 일단 이렇게 풀어야겠다는 감을 잡고서는 구현은 금방 끝낸 문제다.

이번 문제 역시 다른 사람들의 풀이를 보니 정말 멋있는 기술들을 이용해서 푼 사람들이 많던데 난 그런 거 몰라서 그렇게 못 푼다. 그냥 알고 있는 지식들로 어떻게든 풀어내자.

문제 링크 첨부한다.
https://programmers.co.kr/learn/courses/30/lessons/64064

---

문제 해결 순서

유저 ID와 제재 ID들이 입력값으로 주어진다. 내가 가장 먼저 떠올렸던 문제 해결의 순서는 다음과 같다.

1. 제재 ID 별로 매칭 가능한 유저 ID 목록 만들기
2. 위의 목록의 원소로 유저 ID 문자열을 그대로 넣는 것이 아니라, 유저 ID별로 번호를 매겨 문자열 대신 번호 집어넣기
3. 각 제재 ID별 매칭 가능한 번호 그룹들을 백트래킹을 통해 visited[] 에 true로 업데이트하며, 모든 그룹을 다 돌고나면 visited[] 중 true인 놈들만 골라서 하나의 String으로 만들어주기
4. 3번에서 만든 String을 미리 만들어둔 HashSet에 집어 넣기
5. HashSet의 size값이 곧 가능한 모든 case

말로 표현하니까 너무 긴데 아래 내 악필 필기를 통해 조금 더 쉽게 이해해보자.

좌측과 같이 입력이 주어졌을 때, 우측이 가능한 모든 case 를 표현한 것이다. 위의 그림에서는 case 들을 표현하기 위해 유저 ID를 문자열 그대로 표현했다.

하지만 아래와 같이 하면 훨씬 더 간단하고 직관적으로 알 수 있다.

각 유저 ID 값들에게 고유한 인덱스 번호를 붙여주어 번호만으로 소통할 수 있게 된다.

이렇게 문제를 해결해 나가면 된다. 그럼 이제 위의 순서들 중 가장 핵심적인 순서 두 가지를 살펴보자.

---

주어진 불량 ID별로 매치 가능한 유저 ID 목록 만들기

각 제재 ID를 바깥 for문, 각 유저 ID를 안쪽 for문으로 위치시킨다.
제재 ID당 모든 유저 ID를 다 비교하며 매치 가능한 유저 ID들을 저장해주는 작업을 한다.
우선 두 녀석의 길이를 비교하고 서로 다르면 패스, 그 다음은 각 문자별로 순회하며 서로 다르면 패스하는 식으로 비교를 진행하면 된다.

아래는 내가 작성한 매칭 가능한 모든 유저 ID 목록을 만드는 메소드의 코드다.

static ArrayList<Integer>[] createPossibleAbusers(String[] user_id, String[] banned_id){
        ArrayList<Integer>[] result = new ArrayList[banned_id.length];
        for(int banned=0; banned<banned_id.length; banned++){
            ArrayList<Integer> tmp = new ArrayList<>();
            for(int user=0; user<user_id.length; user++){
                boolean flag = true;
                if(banned_id[banned].length()!=user_id[user].length())  continue; // 서로 길이 다르면 패스
                for(int i=0; i<user_id[user].length(); i++){
                    if(banned_id[banned].charAt(i)=='*') continue;
                    if(user_id[user].charAt(i)!=banned_id[banned].charAt(i)) {
                        flag = false;
                        break;
                    }
                }
                if(flag)    tmp.add(user);
            }
            result[banned] = new ArrayList<>(tmp);
        }
        return result;
    }

---

백트래킹을 통한 가능한 case 카운팅

위에서 매치 가능한 모든 유저 ID 목록들을 완성하고 나면 그 목록들을 순회하며 모든 가능한 case들을 카운팅해주자.

각 제재 ID별로 가능한 유저 ID 목록들을 순회하며 아직 방문하지 않은 녀석들을 대상으로 방문해주고 모든 제재 ID들을 다 돌았으면 visited[] 배열 중에 true 체크가 된 인덱스들을 String으로 만들어줘서 HashSet에 추가한다.

재귀를 다 마치고 나면 HashSet에 추가된 String의 개수가 곧 가능한 모든 case 의 수가 되는 것이다.

아래는 내가 작성한 백트래킹 메소드 코드다.

static void backTracking(int cnt, int user_id_size, int banned_id_size){
        if(cnt==banned_id_size){
            String s = "";
            for(int i=0; i<user_id_size; i++)
                if(visited[i])  s += i;

            set.add(s);
            return;
        }

        ArrayList<Integer> cur = possibleAbusers[cnt];
        for(int i=0; i<cur.size(); i++){
            if(visited[cur.get(i)]) continue;
            visited[cur.get(i)] = true;
            backTracking(cnt+1, user_id_size, banned_id_size);
            visited[cur.get(i)] = false;
        }
    }

---

아래는 내가 제출한 위의 과정을 모두 합친 코드다.

import java.util.*;
import java.io.*;

public class Abuser {
    static HashSet<String> set = new HashSet<>();
    static ArrayList<Integer>[] possibleAbusers;
    static boolean[] visited;

    static int solution(String[] user_id, String[] banned_id) {
        visited = new boolean[user_id.length];
        possibleAbusers = createPossibleAbusers(user_id, banned_id);
        backTracking(0, user_id.length, banned_id.length);
        return set.size();
    }

    static void backTracking(int cnt, int user_id_size, int banned_id_size){
        if(cnt==banned_id_size){
            String s = "";
            for(int i=0; i<user_id_size; i++)
                if(visited[i])  s += i;

            set.add(s);
            return;
        }

        ArrayList<Integer> cur = possibleAbusers[cnt];
        for(int i=0; i<cur.size(); i++){
            if(visited[cur.get(i)]) continue;
            visited[cur.get(i)] = true;
            backTracking(cnt+1, user_id_size, banned_id_size);
            visited[cur.get(i)] = false;
        }
    }

    static ArrayList<Integer>[] createPossibleAbusers(String[] user_id, String[] banned_id){
        ArrayList<Integer>[] result = new ArrayList[banned_id.length];
        for(int banned=0; banned<banned_id.length; banned++){
            ArrayList<Integer> tmp = new ArrayList<>();
            for(int user=0; user<user_id.length; user++){
                boolean flag = true;
                if(banned_id[banned].length()!=user_id[user].length())  continue; // 서로 길이 다르면 패스
                for(int i=0; i<user_id[user].length(); i++){
                    if(banned_id[banned].charAt(i)=='*') continue;
                    if(user_id[user].charAt(i)!=banned_id[banned].charAt(i)) {
                        flag = false;
                        break;
                    }
                }
                if(flag)    tmp.add(user);
            }
            result[banned] = new ArrayList<>(tmp);
        }
        return result;
    }

    public static void main(String args[]) throws IOException {
        BufferedWriter bfw = new BufferedWriter(new OutputStreamWriter(System.out));
        String[] users = {"frodo", "fradi", "crodo", "abc123", "frodoc"};
        String[] banned = {"fr*d*", "abc1**"};

        bfw.write(String.valueOf(solution(users,banned)));
        bfw.close();
    }
}

오늘 배운 것

1. 주어진 입력값들을 무조건 그대로 사용한다는 고정관념에서 벗어날 필요가 있다. 주어진 ID들을 String 그대로 사용하는 것이 아니라 index 번호를 매겨 다루는 것과 같이 말이다.
2. 여전히 내가 아는 지식의 크기에 대한 한계를 느낀다. 하지만 내가 아는 것만으로 어떻게든 풀어내려고 해보자.