프로그래머스 - 불량 사용자 (C++)

맨날 적당히 머리굴리다가 구글링을 해버리는 제 자신이 프로그래머스 불량 사용자가 아닐까 싶습니다.

프로그래머스

---

일단 이 문제는 데이터의 크기가 작습니다. user_id는 최대 8이고 banned_id도 최대 8, 아이디의 길이도 8입니다. 따라서 시간초과에 비교적 부담없이 풀이를 구상해도 좋습니다. 저같은 경우에는 가벼운 마음으로 next_permutation()을 사용할 수 있었습니다(참고로 데이터가 N개일때 next_permutation의 시간복잡도는 O(N*N!)입니다).

문제 해결에서 고려할 요소는 아래와 같습니다.

1. 하나의 banned_id에 하나의 user_id만 매칭시키면 됨

2. 중복되는 banned_id가 존재함 => 아이디 목록의 내용이 동일하면 하나의 경우로 처리

 

2번의 경우때문에 매 순회마다 불량 사용자들을 걸러낸 뒤에 중복처리를 해줘야 합니다. 정렬도 필요하고 중복처리도 해줘야하기 때문에 중복처리+정렬을 해주는 자료구조인 set을 사용합니다.

 

전체 솔루션 코드는 아래와 같습니다. 아래에 간단한 설명이 있습니다.

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

using namespace std;

bool matching(string user, string ban) {
    if(user.size() != ban.size()) return false;
    
    int index = 0;
    while(index < user.size()) {
        if(ban[index] == '*' || user[index] == ban[index]) {
            index++;
        } else {
            return false;
        }
    }
    return true;
}

int solution(vector<string> user_id, vector<string> banned_id) {
    int answer = 0;
    set<string> idset;
    sort(user_id.begin(), user_id.end());
    do {
        set<string> matching_ids;

        for(int i = 0; i < banned_id.size(); i++) {
            if(matching(user_id[i], banned_id[i])) {
                matching_ids.insert(user_id[i]);
            }
        }
        
        if(matching_ids.size() != banned_id.size()) continue;
        
        string idstrings = "";
        for(string id : matching_ids) {
            idstrings += id;
        }
        idset.insert(idstrings);
            
    } while(next_permutation(user_id.begin(), user_id.end()));
    
    return idset.size();
    
}

• matching()함수는 인자로 받는 user_id가, 역시 인자로 받게되는 banned_id에 걸리는 녀석인지 확인합니다.
• solution은 do-while문과 내부에 2개의 for문으로 구성되있습니다.
  • 먼저 next_permutation으로 user_id를 돌리기 위해 User_id를 정렬해줍니다.
  • 첫번째 for문에서는 banned_id의 길이만큼 순회를 합니다. banned_id의 i번째 원소와 user_id의 i번째 원소를 비교합니다. 이 부분에서 살짝 의문이 들수도 있지만(저는 살짝 헷갈렸습니다) 어차피 next_permutation으로 모든 경우를 고려하기 때문에 이 방법이 맞습니다.
  • 매칭되는 id라면 matching_ids라는 set에 넣어줍니다. 알아서 중복&정렬을 해줍니다.
  • 그다음, banned_id의 개수만큼 매칭되는 id들을 찾았다면 idstring이라는 문자열에 matching_ids의 원소를 순서대로 넣어줍니다.
  • 그다음에 idset이라는 set에 idstring을 넣어주는데, 왜? => 아이디 목록의 내용이 동일하면 하나의 경우로 처리해줘야 하기 때문입니다.
    • string으로 그냥 막 밀어넣어도 괜찮은걸까 싶지만 어차피 우리가 원하는건 string이든 뭐든 중복인지 아닌지만 확인하면 되기때문에 상관없습니다. 실제로는 [frodo, abc123] 같은 형태의 데이터지만 "frodoabc123"이렇게 넣는다고 중복처리에 문제가 되진 않는 상황이니까요.
• 모든 순열을 다 탐색했다면 마지막에 idset.size()를 리턴하면 됩니다.

---

 

데이터가 적은걸 빠르게 캐치하고 적당한 완전탐색 방법을 찾는것도 중요한것 같습니다.