[2019 kakao winter internship] 03. 불량 사용자 (cpp/python)

불량 사용자

프로그래머스

 

 

문제 설명

user_id 중에서 banned_id의 조건에 맞는 원소를 뽑는 조합 문제다. 단, banned_id의 조건에 맞는 원소를 뽑을 때 중복이 생길 수 가 있는데 이 중복을 피하는게 키포인트 인 문제이다.

백트래킹을 이용한 조합을 구현하고 ``을 이용하여 중복을 제거했다.

문제 풀이

소스코드 : C++

1. user_id를 사용 여부를 체크하기위한 vector chk를 user_id 사이즈 만큼 할당해준다.
2. 백트래킹을 이용한 조합구현 process()를 진행한다.
   1. uid가 사용한 적이 없고 bid와 길이가 같다면
   2. uid와 bid를 비교하여 매핑될 수 없는 경우는 flag=false하고 break를 걸어준다.
   3. 매핑될수 있는 경우에는 찾은 원소의 인덱스를 매개변수 res에 누적시켜준다.
   4. 다음 원소를 찾기 위해 재귀호출을 한다.
3. banned_id의 길이만큼 모두 찾았다면 누적된 res를 정렬(순열이 아닌 조합이기 때문에)하고 set s에 넣어준다.
4. 모든 과정이 끝나고 s의 길이를 답으로 출력하면 된다.

#include <iostream>
#include <string>
#include <vector>
#include <unordered_map>
#include <algorithm>
#define PLL pair<long long,long long>
#define ll long long
#define endl '\n'


using namespace std;
vector<long long> answer;
unordered_map<ll, PLL> m;     //배정 받은 방번호, {배정 받은 사람, 다음 방 번호}
ll find_room(ll i, ll key){
    if(m.find(key)==m.end()){
        m.insert({key,{i,key+1}});
        answer.push_back(key);
        return key+1;
    }
    else{ 
        ll nk = find_room(i, m[key].second);
        m[key].second = nk;
        return nk;
    }
}
vector<long long> solution(long long k, vector<long long> room_number) {
    for(ll i=0; i<room_number.size(); i++){
        ll key = room_number[i];
        if(m.find(key)==m.end()){
            m.insert({key,{i,key+1}});
            answer.push_back(key);
        }
        else{
            m[key].second = find_room(i,m[key].second);
        }
    }

    // vector<PLL> tmp;
    // for(auto res : m){
    //     tmp.push_back({res.second.first, res.first});
    // }
    // sort(tmp.begin(), tmp.end());
    // for(auto ans : tmp)
    //     answer.push_back(ans.second);    
    return answer;
}
int main(){
    ll k;
    vector<ll> rn;

    k=10;
    rn = {1,3,4,1,3,1};

    for(auto ans : solution(k,rn))
        cout<<ans<<endl;

    return 0;
}

소스코드 : Python

위 cpp로 푼 풀이와 큰 차이는 없다. 다만 vector chk대신 비트마스크를 활용해봤다.

비트마스크를 사용하면 $O(N)$ 의 탐색시간을 $O(1)$로 줄일 수 있다.

chk = 0b00000000 
s = [] 
def comb(user_id, banned_id,cnt): 
    global chk 
    if cnt == len(banned_id): 
        print(chk in s) 
        if chk in s==False: 
            print("ok") 
            s.append(chk) 
        print(s) 
        return 
    bid = banned_id[cnt] 
    for i in range(len(user_id)): 
        uid = user_id[i] 
        if len(bid)==len(uid) and chk & (1<<i) == False: 
            flag = True 
            for j in range(len(bid)): 
                if bid[j] != "*" and bid[j]!=uid[j]: 
                    flag = False 
                    break 

            if flag: 
                chk +=1<                comb(user_id, banned_id,cnt+1) 
                chk -=1<def solution(user_id, banned_id): 
    answer = 0 
    s =[] 
    comb(user_id, banned_id,0) 
    answer = len(s) 

    return answer 



input_uid = ["frodo", "fradi", "crodo", "abc123", "frodoc"] 
input_bid = ["fr*d*", "abc1**"] 

# input_uid = ["frodo", "fradi", "crodo", "abc123", "frodoc"] 
# input_bid = ["*rodo", "*rodo", "******"] 

# input_uid = ["frodo", "fradi", "crodo", "abc123", "frodoc"] 
# input_bid = ["fr*d*", "*rodo", "******", "******"] 

print(solution(input_uid, input_bid))