[프로그래머스] 불량 사용자 / C++
문제 설명
개발팀 내에서 이벤트 개발을 담당하고 있는 무지는 최근 진행된 카카오 이모티콘 이벤트에 비정상적인 방법으로 당첨을 시도한 응모자들을 발견하였습니다. 이런 응모자들을 따로 모아 불량 사용자라는 이름으로 목록을 만들어서 당첨 처리 시 제외하도록 이벤트 당첨자 담당자인 프로도 에게 전달하려고 합니다. 이때 개인정보 보호를 위해 사용자 아이디 중 일부 문자를 '*' 문자로 가려서 전달했습니다. 가리고자 하는 문자 하나에 '*' 문자 하나를 사용하였고 아이디 당 최소 하나 이상의 '*' 문자를 사용하였습니다.
무지와 프로도는 불량 사용자 목록에 매핑된 응모자 아이디를 제재 아이디 라고 부르기로 하였습니다.
예를 들어, 이벤트에 응모한 전체 사용자 아이디 목록이 다음과 같다면
응모자 아이디 |
frodo |
fradi |
crodo |
abc123 |
frodoc |
다음과 같이 불량 사용자 아이디 목록이 전달된 경우,
불량 사용자 |
fr*d* |
abc1** |
불량 사용자에 매핑되어 당첨에서 제외되어야 야 할 제재 아이디 목록은 다음과 같이 두 가지 경우가 있을 수 있습니다.
제재 아이디 |
frodo |
abc123 |
제재 아이디 |
fradi |
abc123 |
이벤트 응모자 아이디 목록이 담긴 배열 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 |
코드
#include <string>
#include <vector>
#include <unordered_map>
using namespace std;
// 제재 아이디의 조합을 저장
// 순서를 고려하지 않으므로 um.size()가 경우의 수
unordered_map<string, int> um;
// 제재 아이디와 일치하는지 확인
bool match(string &a, string &b)
{
// 길이가 다르면 다른 아이디
if (a.size() != b.size())
return false;
// '*' 이외의 부분이 다르면 다른 아이디
for (int i = 0; i < a.size(); i++)
{
if (b[i] == '*')
continue;
if (a[i] != b[i])
return false;
}
return true;
}
// 제재 아이디의 모든 조합을 확인
// idx : banned_id의 인덱스
// select : select[i]는 user_id[i]의 선택 여부를 의미 (0: 선택X, 1: 선택O)
void dfs(int idx, string &select, vector<string> &user_id, vector<string> &banned_id)
{
// 모든 제재 아이디를 선택했으면 조합에 추가
if (idx == banned_id.size())
{
um[select]++;
return;
}
// 모든 아이디 확인
for (int i = 0; i < user_id.size(); i++)
{
// 이미 선택된 아이디라면 패스
if (select[i] == '1')
continue;
// 제재 아이디와 일치하면 선택하고 다음 dfs() 수행
// dfs() 수행 후에는 다음 경우를 확인하기 위해 선택을 해제
if (match(user_id[i], banned_id[idx]))
{
select[i] = '1';
dfs(idx + 1, select, user_id, banned_id);
select[i] = '0';
}
}
}
int solution(vector<string> user_id, vector<string> banned_id)
{
int answer = 0;
string select = "00000000";
dfs(0, select, user_id, banned_id);
answer = um.size();
return answer;
}
링크
programmers.co.kr/learn/courses/30/lessons/64064
github.com/inbdni/Programmers/blob/master/level03/%EB%B6%88%EB%9F%89%EC%82%AC%EC%9A%A9%EC%9E%90.cpp