[프로그래머스/Java] 64064번 불량 사용자

프로그래머스 불량 사용자 [2019 카카오 개발자 겨울 인턴십]
https://programmers.co.kr/learn/courses/30/lessons/64064

어렵게 생각하니 더욱 풀 수 없었던 문제.
결국은 DFS와 Set이 답이었고, 조합을 직접 고민할 필요도 없었다.

import java.util.*;
class Solution {
    Set<Integer> resultSet = new HashSet<>();
    public int solution(String[] user_id, String[] banned_id) {
        int answer = 0;
        int banLen = banned_id.length, userLen = user_id.length;
        boolean[][] map = new boolean[banLen][userLen];
        for(int i = 0 ; i < banLen ; i++){
            for(int j = 0 ; j < userLen ; j++){
                if(match(banned_id[i], user_id[j])) map[i][j] = true;
            }
        }
        dfs(banLen, userLen, map, new boolean[userLen], 0);
        return resultSet.size();
    }
    public void dfs(int banLen, int userLen, boolean[][] map, boolean[] visited, int index){
        if(index >= banLen){
            int result = 0;
            for(int i = 0 ; i < userLen ; i++)
                if(visited[i]) result += 2 << i;
            resultSet.add(result);
            return;
        }
        int count = 0;
        for(int j = 0 ; j < userLen ; j++){
            if(map[index][j] && !visited[j]){
                visited[j] = true;
                dfs(banLen, userLen, map, visited, index+1);
                visited[j] = false;
            }
        }
    }
    public boolean match(String a, String b){
        if (a.length() != b.length()) return false;
        int len = a.length();
        for(int i = 0 ; i < len ; i++){
            if(a.charAt(i) != '*' && a.charAt(i) != b.charAt(i)) return false;
        }
        return true;
    }
}

.
.

통과한 코드에서는 가능한 user id 조합을 Integer로 표현하고 Set에 넣어 중복을 막았는데,
사실 실패한 코드에서는 먼저 중복을 고려하지 않은 채 count하고 중복 가능한 개수만큼 나누었다.

예시로 표현하자면
user id가 ["frodo", "fradi", "crodo", "abc123", "frodoc"]
banned id가 ["*rodo", "*rodo", "******"] 일 때,

banned_id에 가능한 매핑이 아래의 네가지이고,
["frodo", "crodo", "abc123"]["frodo", "crodo", "frodoc"]
["crodo", "frodo", "abc123"]["crodo", "frodo", "frodoc"]
banned_id에 *rodo가 두 개 있으므로
4/2! = 2를 result로 만드는 식이었다.

이 경우, 입출력 예의 테스트 코드는 통과하지만 결국 틀린 코드였다.
아래와 같은 반례가 있기 때문이다.

user id가 ["frido", "frodo"]이고
banned_id가 ["fr*do", "fr**o"]라고 해보자.
내 방식대로 한다면 ["frido", "frodo"], ["frodo", "frido"] 두 케이스를 구한 뒤
banned_id에 중복이 없으므로 result로 2를 리턴할 것이다.

하지만 두 케이스는 결국 동일한 케이스로 result가 1이어야 정답이다.

.
.

알고리즘은 간단한 아이디어라도 문제와 연결지을 수 있어야하고,
반례를 충분히 고민할 수 있을 때 잘 풀 수 있다는 걸 새삼스레 또 깨달았다.