오늘 푼 두번째 문제는 프로그래머스 불량 사용자 이다. 하 너무 속상하다,, 빨리 더 잘 풀 수 있었는데 돌아 돌아 오래 걸렸다,, ㅜ 너무 어렵게 생각했던 것도 있고 평소 쓰던 함수에 대해 제대로 이해하지 않고 있었다,,! 시험전에 알게된게 어디야,,,! 괜차나,,!!!😭😭😭
프로그래머스 불량 사용자
개발팀 내에서 이벤트 개발을 담당하고 있는 "무지"는 최근 진행된 카카오이모티콘 이벤트에 비정상적인 방법으로 당첨을 시도한 응모자들을 발견하였습니다. 이런 응모자들을 따로 모아 불량 사용자라는 이름으로 목록을 만들어서 당첨 처리 시 제외하도록 이벤트 당첨자 담당자인 "프로도" 에게 전달하려고 합니다. 이 때 개인정보 보호을 위해 사용자 아이디 중 일부 문자를 '' 문자로 가려서 전달했습니다. 가리고자 하는 문자 하나에 '' 문자 하나를 사용하였고 아이디 당 최소 하나 이상의 '*' 문자를 사용하였습니다.
"무지"와 "프로도"는 불량 사용자 목록에 매핑된 응모자 아이디를 제재 아이디 라고 부르기로 하였습니다.
예를 들어, 이벤트에 응모한 전체 사용자 아이디 목록이 다음과 같다면
| 응모자 아이디 |
|---|
| frodo |
| fradi |
| crodo |
| abc123 |
| frodoc |
다음과 같이 불량 사용자 아이디 목록이 전달된 경우,
| 불량 사용자 |
|---|
| frd |
| 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 의 최대 길이가 8 이기 때문에 그저 단순하게 brute-force 방법을 적용해도 괜찮은데,, 괜히 뭐 길이별로 정렬하고,, substring 쓰고,, set 으로 해볼까,,? 생각하다가 시간만 낭비했다,,!
그냥 단순히 모든 경우의 수를 확인한다.
user_id 의 아이디 중에서 banned_id 갯수 만큼 아이디를 뽑고 매칭이 가능한 경우를 확인하는 방식이다.
먼저 user_id 에서 banned_id 의 길이 r 만큼의 아이디를 뽑아 2차원 배열 vector<vector<int>> combinations 에 담았다.
이후 각 조합 마다 매칭이 가능한지를 확인하는데, 이 과정에서 시간을 많이 사용했다. 이유는 자주 사용해 오던 <algorithm> 의 next_permutation 함수를 제대로 이해하고 있지 않아서였다.
뽑은 아이디들이 담긴 combination[i] 와 banned_id 가 서로 매칭이 가능한지 isMapped 함수에서 확인하는데 이때 주의할 점은 combination[i]에 담긴 아이디들의 순열에 따라서 매칭이 될수도, 안될 수도 있다는 점이다. 이 역시 그냥 모든 순열을 확인하기로 하였다. 어설픈 머리를 굴리는 것 보다 경우의 수가 크지 않기 때문에 단순히 하는 것이 더 빠를 것이라 판단했다.
combination[i] 와 banned_id 의 길이는 동일하기 때문에 combination[i][j] 와 banned_id[j] 가 문자 ' * '를 제외하고 일치하는지를 확인하고 일치 하지 않는 경우가 있다면 combination[i]의 순서를 바꾸어서 다시 확인한다.
이 과정에서 역시나 next_permatation 을 사용하였는데 next_permatation 은 더 큰 순열로 재배열이 가능하면 재배열하는 방식이기 때문에 모든 경우의 수를 빠짐없이 확인하려면 반드시 순열을 구할 원소들이 정렬되어 있어야 한다!!!
이 점을 몰랐다,, 난 정말,, 하나는 알고,, 둘은 모르는,, 찌방 ㅜ 😭 그래도 이건 절대 까먹지 않겠다,, 하는 생각으로 셀프 토닥,,ㅋ
암튼 그 점을 몰라서 도대체 왜 모든 경우가 확인안되는거지?????? 라는 내적 외침만 외치면서 시간이 흘러흘러~ 갔고,, 겨우 깨닫고 고쳐서 통과 했다,,!
코드
#include <string>
#include <vector>
#include <algorithm>
using namespace std;
// 문자열 매칭 확인
bool isPossible(string origin, string ban){
for (int i = 0; i < origin.length(); ++i) {
if (ban[i] == '*') continue;
if (origin[i] != ban[i]) return false;
}
return true;
}
// 매칭 가능 확인
bool isMapped(vector<string> id, vector<string> banned){
sort(id.begin(), id.end()); // 반드시 정렬되어 있어야!!! 모든 경우의 수 확인 가능!!!
do{
bool match = true;
for (int i = 0; i < id.size(); ++i) {
// 길이가 다르면 확인 필요 없음, 길이가 같으면 두 문자열 매칭 되는지 확인
if (id[i].length() != banned[i].length() || !isPossible(id[i], banned[i])){
match = false;
break;
}
}
if (match) return true;
}while (next_permutation(id.begin(), id.end()));
return false;
}
int solution(vector<string> user_id, vector<string> banned_id) {
int answer = 0;
int n = user_id.size(), r = banned_id.size();
vector<bool> select(n-r, false);
for (int i = 0; i < r; ++i) select.push_back(true);
// user_id에서 r개의 아이디 뽑기
vector<vector<string>> combinations;
do{
vector<string> picked;
for (int i = 0; i < n; ++i) {
if (select[i]) picked.push_back(user_id[i]);
}
combinations.push_back(picked);
}while (next_permutation(select.begin(), select.end()));
// 각 조합별로 모든 순열에 대해서 매칭이 한번이라도 가능하면 경우의 수 ++;
for (int i = 0; i < combinations.size(); ++i) {
if(isMapped(combinations[i], banned_id)) answer++;
}
return answer;
}