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

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

프로그래머스

<풀이>

1. 제재 아이디가 가능한 모든 경우를 계산한다.

2. 중복되는 제재 아이디 경우를 제외합니다.

3. 모든 경우의 수를 출력합니다.

 

<해법>

1. 제재 아이디가 가능한 모든 경우를 계산하는 방법.

=> 모든 경우를 시뮬레이션 하는 대표적인 방법으로 '백트래킹'이 있습니다. 위 문제에서 저는 '백트래킹'을 재귀함수로 구현하였습니다. 저는 재귀함수로 구현하기 이전에 아래와 같은 그림으로 대표적인 틀을 잡습니다.

 

2. 중복되는 경우를 제외하는 방법.

=> 위 문제에서 중복되는 경우는 두 가지가 있습니다. 아이디가 중복되서는 안되며, 나열된 아이디 내용들이 중복되서는 안됩니다. 

(1) 아이디 중복 제외

저는 방문 배열을 이용하여 이전 단계에서 제재 아이디로 탐색된 경우, 탐색을 할 수 없도록 하였습니다.

(2) 나열된 아이디 내용들 중복 제외

저는 자료구조 'set'를 사용하였습니다. 'set'를 이용하여 중복된 내용이 담겼을 경우 제외되도록 하였습니다.

#include <iostream>
#include <string>
#include <vector>
#include <set>
using namespace std;
 
vector<string> user;
vector<string> banned;
bool visited[10];
set<string> s;
 
void go(int index) {
 
    //종료조건 : 모든 불량 사용자 아이디 탐색 완료
    if (index == banned.size()) {
 
        //제재 아이디로 등록된 아이디 한 문자열로 만들기
        string tmp = "";
        for (int i = 0; i < user.size(); i++) {
            if (visited[i]) {
                tmp += user[i];
            }
        }
 
        //세트로 중복 제거
        s.insert(tmp);
        return;
    }
 
    //불량 사용자 아이디 마다 가능한 제재 아이디 탐색
    for (int i = 0; i < user.size(); i++) {
 
        bool isAble = true;
        
        //이전 탐색에서 제재 아이디로 등록된 경우 -> 불가능
        if (visited[i]) {
            continue;
        }
 
        //아이디 길이가 다를 경우 -> 불가능
        if (user[i].length() != banned[index].length()) {
            continue;
        }
 
        //각 문자 비교 탐색
        for (int j = 0; j < user[i].length(); j++) {
            if (banned[index][j] == '*') {
                continue;
            }
            //문자가 다를경우 -> 불가능
            if (banned[index][j] != user[i][j]) {
                isAble = false;
                break;
            }
        }
 
        //제재 아이디가 가능한 경우 -> 다음 단계
        if (isAble) {
            visited[i] = true;
            go(index + 1);
            visited[i] = false;
        }
    }
    return;
}
 
int solution(vector<string> user_id, vector<string> banned_id) {
    int answer = 0;
 
    user = user_id;
    banned = banned_id;
 
    //재귀함수 시작
    go(0);
 
    //결과 저장
    answer = s.size();
 
    return answer;
}

 

백트래킹에 대해 알아볼 수 있는 문제였습니다.