[프로그래머스] 불량 사용자

---

📌 문제 설명

개발팀 내에서 이벤트 개발을 담당하고 있는 "무지"는 최근 진행된 카카오이모티콘 이벤트에 비정상적인 방법으로 당첨을 시도한 응모자들을 발견하였습니다. 이런 응모자들을 따로 모아 불량 사용자라는 이름으로 목록을 만들어서 당첨 처리 시 제외하도록 이벤트 당첨자 담당자인 "프로도" 에게 전달하려고 합니다. 이 때 개인정보 보호을 위해 사용자 아이디 중 일부 문자를 '*' 문자로 가려서 전달했습니다. 가리고자 하는 문자 하나에 '*' 문자 하나를 사용하였고 아이디 당 최소 하나 이상의 '*' 문자를 사용하였습니다.
"무지"와 "프로도"는 불량 사용자 목록에 매핑된 응모자 아이디를 제재 아이디 라고 부르기로 하였습니다.

 

이벤트 응모자 아이디 목록이 담긴 배열 user_id와 불량 사용자 아이디 목록이 담긴 배열 banned_id가 매개변수로 주어질 때, 당첨에서 제외되어야 할 제재 아이디 목록은 몇가지 경우의 수가 가능한 지 return 하도록 solution 함수를 완성해주세요.

 

📌 제한 사항

• user_id 배열의 크기는 1 이상 8 이하입니다.
• user_id 배열 각 원소들의 값은 길이가 1 이상 8 이하인 문자열입니다.
  • 응모한 사용자 아이디들은 서로 중복되지 않습니다.
  • 응모한 사용자 아이디는 알파벳 소문자와 숫자로만으로 구성되어 있습니다.
• banned_id 배열의 크기는 1 이상 user_id 배열의 크기 이하입니다.
• banned_id 배열 각 원소들의 값은 길이가 1 이상 8 이하인 문자열입니다.
  • 불량 사용자 아이디는 알파벳 소문자와 숫자, 가리기 위한 문자 '*' 로만 이루어져 있습니다.
  • 불량 사용자 아이디는 '*' 문자를 하나 이상 포함하고 있습니다.
  • 불량 사용자 아이디 하나는 응모자 아이디 중 하나에 해당하고 같은 응모자 아이디가 중복해서 제재 아이디 목록에 들어가는 경우는 없습니다.
• 제재 아이디 목록들을 구했을 때 아이디들이 나열된 순서와 관계없이 아이디 목록의 내용이 동일하다면 같은 것으로 처리하여 하나로 세면 됩니다.

📌 입출력 예

 

user_id	banned_id	result
["frodo", "fradi", "crodo", "abc123", "frodoc"]	["fr*d*", "abc1**"]	2
["frodo", "fradi", "crodo", "abc123", "frodoc"]	["*rodo", "*rodo", "******"]	2
["frodo", "fradi", "crodo", "abc123", "frodoc"]	["fr*d*", "*rodo", "******", "******"]	3

🔗 문제 링크

https://school.programmers.co.kr/learn/courses/30/lessons/64064

프로그래머스

---

반응형

💡 풀이 아이디어

• banned_id에서 가능한 user_id 찾기
• 찾은 id들을 조합하여 경우의 수 찾기

📝 최종 풀이

• banned_id마다 가능한 user_id를 모두 찾아 vector<vector<string>> id_case에 저장합니다.
• 백트래킹을 통해 가능한 모든 조합을 탐색합니다.
  • 중복되는 경우를 제외하기 위해 unordered_set을 사용

---

728x90

👩‍💻 코드

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

using namespace std;

void findCases(int index, vector<vector<string>>& id_case, vector<string>& current, unordered_set<string>& answer) {
    if (index == id_case.size()) {
        vector<string> sorted_current = current;
        string case_key;
        
        sort(sorted_current.begin(), sorted_current.end());
        
        for (const string& id : sorted_current) {
            case_key += id + ",";
        }
        
        answer.insert(case_key);
        
        return;
    }

    for (const string& user : id_case[index]) {
        if (find(current.begin(), current.end(), user) != current.end()) {
            continue;
        }
        
        current.push_back(user);
        findCases(index + 1, id_case, current, answer);
        current.pop_back();
    }
}

int solution(vector<string> user_id, vector<string> banned_id) {
    int b_size = banned_id.size();
    int u_size = user_id.size();
    vector<vector<string>> id_case(b_size);
    
    for(int i=0; i<b_size; i++){
        for(int j=0; j<u_size; j++){
            if(banned_id[i].size() != user_id[j].size()){
                continue;
            }
            
            bool isWrong = false;
            
            for(int k=0; k<user_id[j].size(); k++){
                if(banned_id[i][k] == '*'){
                    continue;
                }
                
                if(banned_id[i][k] != user_id[j][k]){
                    isWrong = true;
                    break;
                }
            }
            
            if(!isWrong){
                id_case[i].push_back(user_id[j]);
            }
        }
    }
    
    unordered_set<string> answer;
    vector<string> current;

    findCases(0, id_case, current, answer);
    
    return answer.size();
}