programmers [C++] : 2019 카카오 개발자 겨울 인턴십 - 불량사용자

programmers.co.kr/learn/courses/30/lessons/64064#

코딩테스트 연습 - 불량 사용자

문제 설명

---

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

 

접근 방법

---

먼저 banned_id 리스트로 만들수 있는 모든 경우의 수를 구합니다. 그 과정에서 만들어진 목록을 string으로 하나로 만들도록 했습니다. 

그리고 이렇게 만들어진 string 백터에서 중복을 제거하면  끝~ level 3번 치고 쉬운 문제였네요 ^0^~

 

코드 

---

#include <cstring>
#include <vector>
#include <iostream>
#include <algorithm>

using namespace std;

vector<int>astro;
vector<string>ans;
vector<string>container;
bool isused[10];
int cnt=0;
bool compare(string a,string b){
    if(a.length()>b.length()) return false;
    else if(a.length()<b.length()) return true;
    else return a<b;
}
void gd(vector<string> user_id,vector<string> banned_id){
    if(cnt==banned_id.size()){
        vector<string>a;
        a=container;
        sort(a.begin(),a.end(),compare);
        string temp="";
        for(int i=0;i<a.size();i++){
            temp+=a[i];
            temp+=" ";
        }
        ans.push_back(temp);
        return;
    }
    for(int i=0;i<user_id.size();i++){
        //이미 사용된 아이디 제외
        if(isused[i]==true)continue;
        string s1= user_id[i];
        int correct_cnt=0;
        //길이 확인
        if(s1.size()==banned_id[cnt].size()){
            for(int j=0;j<s1.size();j++){
                //각각의 요소 비교
                if(banned_id[cnt][j]=='*'||s1[j]==banned_id[cnt][j]){
                    correct_cnt++;
                    continue;
                }
                else break;
            }
            //같을 경우
            if(correct_cnt==s1.size()){
                container.push_back(s1);
                isused[i]=true;
                cnt++;
                gd(user_id,banned_id);
                isused[i]=false;
                cnt--;
                container.pop_back();
            }
        }
        
    }
}
int solution(vector<string> user_id, vector<string> banned_id) {
    int answer = 0;
    memset(isused,false,sizeof(isused));
    gd(user_id,banned_id);

    sort(ans.begin(),ans.end());
    ans.erase(unique(ans.begin(),ans.end()),ans.end());

    return ans.size();
}

funny algorithm 0_<