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

 

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

 

https://school.programmers.co.kr/learn/courses/30/lessons/64064

프로그래머스

---

 

 

해결전략

 

백트래킹(Backtracking), 집합(Set), 조합(combinations) 

 

해결 방법

1. bool isMatch 함수: user ID가 banned ID과 일치하는지 확인하는  bool 함수 생성.
2. 백트래킹을 통한 조합 생성: 가능한 모든 조합을 생성하고 조건을 만족하는지 확인하는 함수 작성.
3. 중복 제거: 결과 조합에서 중복된 것을 제거하여 최종 답을 구함.

 

이 문제는 계속 실패해서 결국 다른 사람의 풀이를 보았다. 조합을 담을 때 set을 사용한다는것을 생각하기 쉽지 않았다.

 

set<set<string>> result 로 결과를 저장할 집합을 구한다. 이 부분을 기억해야겠다.

---

 

정답코드

 

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

set<set<string>> result; // 결과를 저장할 집합. 각 결과는 중복되지 않은 사용자 ID의 집합이다.
vector<bool> visited;	 // user ID가 사용되었는지를 체크

// 주어진 user ID가 banned ID와 일치하는지 확인
bool isMatch(const string& user, const string& banned)
{
    if (user.size() != banned.size()) return false; // 길이가 다르면 일치X

    for (int i = 0; i < user.size(); i++){ // 각 문자를 비교
        if (banned[i] != '*' && user[i] != banned[i]) return false;
    }

    return true; // 모든 조건을 통과하면 일치
}

// 가능한 모든 조합을 찾는 백트래킹 함수
void FindCombination(const vector<string>& user, const vector<string>& banned, int idx, set<string> currentSet)
{
    if (idx == banned.size()) {
        //for (const auto& iter : currentSet){
        //    cout << iter << ", ";
        //}
        //cout << "\n\n";

        // 모든 banned 패턴을 다 사용한 경우 결과에 현재 조합을 추가
        result.insert(currentSet);
        return;
    }

    for (int i = 0; i < user.size(); i++) // 모든 사용자 ID를 순회
    {
        // 현재 ID가 사용되지 않았고, banned ID와 일치하는 경우
	    if (false == visited[i] && isMatch(user[i], banned[idx]))
	    {
            visited[i] = true;          // 현재 ID를 사용 중으로 표시
            currentSet.insert(user[i]); // 현재 ID를 현재 조합에 추가
            FindCombination(user, banned, idx + 1, currentSet);
            visited[i] = false;         // 백트래킹을 위해 현재 ID 사용 표시를 해제
            currentSet.erase(user[i]);  // 현재 ID를 현재 조합에서 제거
	    }
    }
}

int solution(vector<string> user, vector<string> banned) {
    //visited.clear();
    //result.clear();

	visited.resize(user.size(), false);
    set<string> emptySet;

    FindCombination(user, banned, 0, emptySet); // 백트래킹 시작

    return result.size(); // 가능한 조합의 수 반환
}

int main(){
    vector<string> test1 = { "frodo", "fradi", "crodo", "abc123", "frodoc" };
    vector<string> testcase1 = { "fr*d*", "abc1**" };
    vector<string> test2 = { "frodo", "fradi", "crodo", "abc123", "frodoc" };
    vector<string> testcase2 = { "*rodo", "*rodo", "******" };
    vector<string> test3 = { "frodo", "fradi", "crodo", "abc123", "frodoc" };
    vector<string> testcase3 = { "fr*d*", "*rodo", "******", "******" };

    cout << solution(test1, testcase1) << "\n"; // 출력: 2
    cout << solution(test2, testcase2) << "\n"; // 출력: 2
    cout << solution(test3, testcase3) << "\n"; // 출력: 3

    return 0;
}

 

 

---