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

 

 

문제

문제 설명

 

풀이

 

 

이 문제는 중복된 경우의 수를 제거하는게 핵심인 문제다.

 

먼저 banned_id 와 user_id를 비교해서 ban을 할 수 있는 사용자 목록을 뽑고, ban할 수 있는 경우의 수를 완전 탐색해 풀었다.

 

이 때, 한번 ban할 수 있는 목록으로 뽑힌 사용자가 다시 뽑힐 수 는 없으므로 이 경우를 제거했고, ban할 수 있는 사용자가 전부 뽑히면 Set에 넣어 중복을 제거 했다.

​

​

[아이디어 정리]

1. user중 ban할 수 있는 사용자의 목록을 뽑는다.​
2. ban 할 수 있는 사용자들이 중복되지 않게 뽑고, Set에 넣어 중복을 제거한다.​
3. 최종적으로 구한 Set의 size를 return 한다.

 

 

Code

 

 

#include <string>
#include <vector>
#include <set>
using namespace std;

vector<vector<int>> bannedList;
set<set<int>> answerSet;
bool cmpFunc(string user, string ban)
{
    for (int i=0; i<user.size(); i++)
    {
        if (ban[i]!='*' && user[i]!=ban[i])
        {
            return false;
        }
    }
    return true;
}

void reCalc(int forSize, set<int> mySet)
{
    if (forSize>=0)
    {
        for (int i=0; i<bannedList[forSize].size(); i++)
        {
            if (mySet.find(bannedList[forSize][i])==mySet.end())
            {
                set<int> toSet(mySet);
                toSet.insert(bannedList[forSize][i]);
                reCalc(forSize-1, toSet);
            }
        }
    }
    else
    {
        answerSet.insert(mySet);
    }
}

int solution(vector<string> user_id, vector<string> banned_id) {
    bannedList = vector<vector<int>> (banned_id.size());
    for (int i=0; i<user_id.size(); i++)
    {
        for (int j=0; j<banned_id.size(); j++)
        {
            if (user_id[i].size()==banned_id[j].size())
            {
                if (cmpFunc(user_id[i], banned_id[j]))
                {
                    bannedList[j].push_back(i);
                }
            }
        }
    }
    set<int> a;
    reCalc(banned_id.size()-1, a);
    return answerSet.size();
}

 

---

 

처음에 Set을 안 쓰고 풀어보려고 했는데, 귀찮고 비효율적일 것 같았다.

그리고 Set 사용법도 익혀두는게 좋아서 Set으로 풀었다.

​

Set의 사용법을 익히면서 이중 Set에서 원소를 출력하기 위해 iterator에 대해 다시 공부했다.

이중 set 에서 원소를 출력하고 싶으면, (*iterator).begin()을 사용하거나 iterator->begin() 을 사용하자...

​

나중에 C++ auto도 내용을 자세히 찾아보면 좋을 것 같다.

 

프로그래머스