냄비
문제 설명
개발팀 내에서 이벤트 개발을 담당하고 있는 무지는 최근 진행된 카카오이모티콘 이벤트에 비정상적인 방법으로 당첨을 시도한 응모자들을 발견하였습니다. 이런 응모자들을 따로 모아 불량 사용자라는 이름으로 목록을 만들어서 당첨 처리 시 제외하도록 이벤트 당첨자 담당자인 프로도 에게 전달하려고 합니다. 이 때 개인정보 보호을 위해 사용자 아이디 중 일부 문자를 '*' 문자로 가려서 전달했습니다. 가리고자 하는 문자 하나에 '*' 문자 하나를 사용하였고 아이디 당 최소 하나 이상의 '*' 문자를 사용하였습니다.
무지와 프로도는 불량 사용자 목록에 매핑된 응모자 아이디를 제재 아이디 라고 부르기로 하였습니다.
예를 들어, 이벤트에 응모한 전체 사용자 아이디 목록이 다음과 같다면
응모자 아이디
| 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 |
입출력 예에 대한 설명입출력 예 #1
문제 설명과 같습니다.
입출력 예 #2
다음과 같이 두 가지 경우가 있습니다.
제재 아이디
| frodo |
| crodo |
| abc123 |
제재 아이디
| frodo |
| crodo |
| frodoc |
입출력 예 #3
다음과 같이 세 가지 경우가 있습니다.
제재 아이디
| frodo |
| crodo |
| abc123 |
| frodoc |
제재 아이디
| fradi |
| crodo |
| abc123 |
| frodoc |
제재 아이디
| fradi |
| frodo |
| abc123 |
| frodoc |
구현
해당 문제를 해결하기 위해서는 dfs를 사용해야 한다.
bfs가 아닌 dfs를 사용하는 이유는 깊이 우선 탐색이기 때문에 banned_id만큼 user_id를 탐색하면서 맞는 조합을 모두 탐색해내야 하기 때문이다.
dfs를 재귀로 사용하기 위해서는 다음과 같은 조건을 만족시켜야 한다.
- 탈출조건
- 바꿔야할 것
- 반복조건
1번 탈출조건으로 banned_id로 user_id를 탐색할 때 이미 banned_id의 size만큼 탐색을 완료했으면 탈출하는 것으로 한다.
2번 바꿔야할 것은 banned_id의 조건에 user_id가 만족 시켰을 경우 해당 user_id를 탐색하지 않기 위하여 bool 배열을 만들어 주어서 false로 바꿔준다.
3번 반복조건은 아직 banned_id의 size만큼 탐색을 못했을 경우 dfs를 재귀로 반복시켜준다.
우선 다음과 같이 탈출조건을 만들어 준다.
void dfs(vector<string> u_id, vector<string> b_id, int b_ind) {
int b_size = b_id.size();
int u_size = u_id.size();
if (b_ind >= b_size) {// if b_ind를 늘리면서 재귀를 해줄것인데 이게 b_id 의 사이즈와 같아지면 탈출!
string temp = "";
// 탈출할때 check가 걸려있는것들은
for (int i = 0; i < u_id.size(); i++) {
if (check[i]) {
//temp에 저장 후
temp += i;
}
}
//set에 넣어주고
_set.insert(temp);
return;
}
}우선 user_id와 banned_id와 banned_id의 size를 dfs의 인자로 받아주고 b_ind(banned_id를 0부터 늘려가며 비교해줄 변수)가 b_size(banned_id의 size)를 넘어설 경우 탈출하는 것으로 해준다.
for (int i = 0; i < u_id.size(); i++) {
if (check[i]) {
//temp에 저장 후
temp += i;
}
}
//set에 넣어주고
_set.insert(temp);
return;위 구문은 banned_id의 조건에 맞는 user_id가 생겼을 때 check 재귀구문에서 바꿔줄 것이라서 check가 true일 때만 temp에 더해주고 다 더해준걸 temp에 저장해줄 것이다.
다음 바꿔주는 부분을 다음과 같이 구현한다.
for (int i = 0; i < u_size; i++) {
// if 사이즈가 다르고 check[i]면(해당 id를 다른 b_id가 쓰고있으면) continue
if (b_id[b_ind].size() != u_id[i].size() || check[i]) {
continue;
}
// check = true
bool tmp = true;
// 사이즈가 같으면
// for u_id의 인덱스만큼 돌려줌
for (int j = 0; j < u_id[i].size(); j++) {
// if b_id의 인덱스가 *면 continue
if (b_id[b_ind][j] == '*') {
continue;
}
// if u_id의 인덱스와 b_id의 인덱스가 다르면 check = false , break;
if (u_id[i][j] != b_id[b_ind][j]) {
tmp = false;
break;
}
}
}아래와 같이 banned_id와 user_id의 size가 다르다면 비교할 필요가 없으므로 continue해주고
이미 해당 user_id가 앞에 나왔던 banned_id로 check 됐다면 continue 해준다.
if (b_id[b_ind].size() != u_id[i].size() || check[i]) {
continue;
}
bool tmp = true;만약 위의 조건에서 해당되지 않았으면 우선 해당 user_id가 check된다는 가능성을 두고 true로 생각한 후
다음과 같이 조건에 맞춰서 false로 바꿔준다.
for (int j = 0; j < u_id[i].size(); j++) {
// if b_id의 인덱스가 *면 continue
if (b_id[b_ind][j] == '*') {
continue;
}
// if u_id의 인덱스와 b_id의 인덱스가 다르면 check = false , break;
if (u_id[i][j] != b_id[b_ind][j]) {
tmp = false;
break;
}
}user_id의 모든 문자열을 체크하는데 각 문자열에서
banned_id의 문자열을 체크하면서 만약 banned_id에 *가 온다면(비교할 필요가 없기에) 넘어가주고
user_id와 banned_id의 알파벳이 다르다면 check되지 않기 때문에 false로 바꿔준 후 해당 반복문을 종료한다.
위 과정을 완료 했을 경우 user_id에 들어간 것중에 banned_id에 해당되는 경우에만 tmp는 true로 남아있을 것이고 해당되지 않는다면 false로 바뀐다.
if (tmp) {
// 지금것은 재귀를 해서 들어갔을때 다른 b_id가 사용하면 안되므로 check[i]를 true로
check[i] = true;
// dfs(b_ind+1(현재것에 다음 불량사용자),u_id,b_id)
dfs(u_id, b_id, b_ind + 1);
// 다하고 나오면 지금 b_id는 다음번에 사용해야 하므로 check[i]를 false로
check[i] = false;
}따라서 위와 같이 banned_id가 check 됐을 경우에는 재귀를 반복하며 다음 순으로 넘어가주고 check되지 않을 경우 user_id를 계속 돌아준다.
전체 코드는 아래에서 볼 수 있다.
#include <iostream>
#include <algorithm>
#include <string>
#include <vector>
#include <set>
using namespace std;
bool check[8];
set<string> _set;
void dfs(vector<string> u_id, vector<string> b_id, int b_ind) {
int b_size = b_id.size();
int u_size = u_id.size();
if (b_ind >= b_size) {// if b_ind를 늘리면서 재귀를 해줄것인데 이게 b_id 의 사이즈와 같아지면 탈출!
string temp = "";
// 탈출할때 check가 걸려있는것들은
for (int i = 0; i < u_id.size(); i++) {
if (check[i]) {
//temp에 저장 후
temp += i;
}
}
//set에 넣어주고
_set.insert(temp);
return;
//return
}
for (int i = 0; i < u_size; i++) {
// if 사이즈가 다르고 check[i]면(해당 id를 다른 b_id가 쓰고있으면) continue
if (b_id[b_ind].size() != u_id[i].size() || check[i]) {
continue;
}
// check = true
bool tmp = true;
// 사이즈가 같으면
// for u_id의 인덱스만큼 돌려줌
for (int j = 0; j < u_id[i].size(); j++) {
// if b_id의 인덱스가 *면 continue
if (b_id[b_ind][j] == '*') {
continue;
}
// if u_id의 인덱스와 b_id의 인덱스가 다르면 check = false , break;
if (u_id[i][j] != b_id[b_ind][j]) {
tmp = false;
break;
}
}
// if check = true면
if (tmp) {
// 지금것은 재귀를 해서 들어갔을때 다른 b_id가 사용하면 안되므로 check[i]를 true로
check[i] = true;
// dfs(b_ind+1(현재것에 다음 불량사용자),u_id,b_id)
dfs(u_id, b_id, b_ind + 1);
// 다하고 나오면 지금 b_id는 다음번에 사용해야 하므로 check[i]를 false로
check[i] = false;
}
}
}
int solution(vector<string> u_id, vector<string> b_id) {
dfs(u_id, b_id, 0);
int answer = _set.size();
return answer;
}'Kakao Coding Test > Level3' 카테고리의 다른 글
| 자물쇠와 열쇠 C++ 2019 KAKAO Blind Recruitment (0) | 2020.12.01 |
|---|
댓글