문제

Programmers Lv3, 불량 사용자

핵심

• 입력의 크기가 8이라 구현에 초점을 맞춘다.
• 문제에 처음 접근할 때, 해시 자료구조인 unordered_set 배열에 가능한 목록을 담았다. 예를 들어 아래와 같이 담긴다.

[0]: fradi frodo
[1]: crodo frodo
[2]: frodoc abc123
[3]: frodoc abc123

• dfs를 이용해 순열을 만들고, 중복 순열을 제거하는 과정이 복잡했다. 그 이유는 unordred_set<unordered_set<string>> 자료구조를 사용해서 순열을 저장하려고 했지만, unordered_set<string>에 대한 해시함수와 사용자 비교 정의 함수를 기본적으로 제공해 주지 않는다.
• 이를 별도로 구현하는 건 실수가 생기기 쉽고 시간도 더 오래 걸린다. 따라서 순서는 필요 없지만 set을 사용했다. 하지만, 생각해 보면 set 시간복잡도는 $O(log N)$으로 충분히 빠를뿐더러 의도적으로 많이 충돌을 시키는 데이터에 대해서도 해시와 다르게 $O(log N)$을 보장한다. (이때 해시는 $O(N)$에 동작한다) 코딩테스트에서 set과 unordered_set을 쓸 수 있는 상황이 나오면 가급적 set을 사용해야겠다.
• 문제는 직관적으로 접근할 수 있고, 순열을 구할 수 있다면 쉽게 해결할 수 있다. 아래와 같이 접근했다.

1. banned_id를 순회하며 가능한 id를 s배열에 저장한다.
2. dfs로 s배열에서 하나씩 골라 가능한 순열을 만든다.
3. 해당 순열 전체를 저장할 수 있도록 set<set<string>> ret에 담아 중복 순열을 제거한다.
4. ret 크기가 정답이 된다.

개선

코드

C++

#include <string>
#include <vector>
#include <set>
#include <iostream>

using namespace std;

vector<string> s[8];

bool is_banned_id(string ban, string user) {

    if (ban.length() != user.length())
        return false;

    int idx = -1;
    while (ban[++idx]) {
        if (ban[idx] == '*') {
            continue;
        }
        if (ban[idx] != user[idx])
            return false;
    }
    return true;
}


void dfs(int depth, int n, set<string>& seq, set<set<string>>& ret) {

    if (depth == n) {
        ret.insert(seq);
        return ;
    }
    for (auto e : s[depth]) {
        if (seq.find(e) == seq.end()) {
            seq.insert(e);
            dfs(depth + 1, n, seq, ret);
            seq.erase(e);
        }
    }
}

int solution(vector<string> user_id, vector<string> banned_id) {

    for (int i = 0; i < banned_id.size(); ++i) {
        string banned = banned_id[i];
        for (int j = 0; j < user_id.size(); ++j) {
            if (is_banned_id(banned, user_id[j])) {
                s[i].push_back(user_id[j]);
            }
        }
    }

    int n = banned_id.size();
    set<string> seq;
    set<set<string>> ret;
    dfs(0, n, seq, ret);

    return ret.size()
}

Java

import java.util.*;

class Solution {
    ArrayList<String>[] s = new ArrayList[8];
    
    boolean isBannedId(String ban, String user) {
        
        if (ban.length() != user.length()) return false;

        for (int idx = 0; idx < ban.length(); idx++) {
            if (ban.charAt(idx) == '*') {
                continue;
            }
            if (ban.charAt(idx) != user.charAt(idx)) return false;
        }
        return true;
    }

    void dfs(int depth, int n, Set<String> seq, Set<Set<String>> ret) {
        
        if (depth == n) {
            ret.add(new HashSet<>(seq));
            return;
        }
        
        for (String e : s[depth]) {
            if (!seq.contains(e)) {
                seq.add(e);
                dfs(depth + 1, n, seq, ret);
                seq.remove(e);
            }
        }
    }

    public int solution(String[] user_id, String[] banned_id) {
        
        for (int i = 0; i < banned_id.length; i++) {
            s[i] = new ArrayList<>();
            for (var u : user_id) {
                if (isBannedId(banned_id[i], u)) {
                    s[i].add(u);
                }
            }
        }
        
        Set<String> seq = new HashSet<>();
        Set<Set<String>> ret = new HashSet<>();
        dfs(0, banned_id.length, seq, ret);

        return ret.size();
    }
}