[카카오 코딩 테스트] 불량 사용자

https://tech.kakao.com/2020/04/01/2019-internship-test/

2019 카카오 개발자 겨울 인턴십 코딩 테스트 문제 해설

3번 불량 사용자 문제입니다.

 

처음 문제를 봤을 땐 쉬운 문제라고만 생각했지만, 

쉽게 접근했다가는 엄청 헤멜 수 있는 문제였습니다... 실제 시험이었으면 시간만 잡아먹고 틀렸을 것 같네요..

 

문제 조건을 보면 user_id와 banned_id 배열의 길이가 최대 8 밖에 되지 않습니다.

그래서 전부 검사해주면 되는 문제입니다!

 

전부 검사하지 않으면 ["fradi", "frodo"] / ["fr*d*"] 의 경우는 2가 나와야 하지만 1이 나올 수가 있습니다.

["fradi", "frodo"]와 ["frodo", "fradi"] 두 경우를 모두 검사해줘야 2가 나오고 아니라면 첫번째(fradi)에서 다 걸러지게 되기 때문이죠.. 

처음에는 이런 경우를 생각 못하고 쉽네~ 하고 풀다가 코드를 싹 지우게 됬습니다 ㅠㅠ

 

저는 next_permutation를 활용해서 모든 경우를 확인했습니다.

user_id의 경우는 순서가 바뀌는 경우는 중복될 수도 있기 때문에

따로 0과 1의 조합 배열(comb)을 만들어 수행했습니다. 

 

다른 방법으로는, dfs로 재귀적인 방법으로도 할 수 있을 것 같습니다.

 

아래는 next_permutation으로 구현한 코드입니다.

#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
 
using namespace std;
bool is_equal(string user, string ban) {
    bool flag = false;
    if (user.length() == ban.length()) {
        flag = true;
        for (int k = 0; k < user.length(); k++) {
            if ((user[k] != ban[k]) && ban[k] != '*') {
                flag = false;
                break;
            }
        }
    }
    return flag;
}
int solution(vector<string> user_id, vector<string> banned_id) {
    int answer = 0;
    int user_len = user_id.size();
    int ban_len = banned_id.size();
    vector<int> comb(user_len);
    for (int i = 0; i < user_len; i++) {
        if (i < (user_len - ban_len))
            comb[i] = 0;
        else 
            comb[i] = 1;
    }
    do {
        sort(banned_id.begin(), banned_id.end());
        do {
            int cnt = 0;
            int ban_idx = 0;
            for (int i = 0; i < user_len; i++) {
                if (comb[i] == 1) {
                    if (is_equal(user_id[i], banned_id[ban_idx++])) {
                        cnt++;
                    }
                }
            }
            if (cnt == ban_len) {
                answer++;
                break;
            }
        } while (next_permutation(banned_id.begin(), banned_id.end()));
    } while (next_permutation(comb.begin(), comb.end()));
    return answer;
}
int main() {
    vector<string> user_id = { "frodo", "fradi", "crodo", "abc123", "frodoc" };
    vector<string> banned_id = { "fr*d*", "abc1**" };
    cout << solution(user_id, banned_id);
    system("pause");
    return 0;
}

 

질문이나 지적 사항은 댓글 부탁드립니다 :)