Programmers - 불량 사용자

---

title: Programmers - 불량 사용자
date: 2022-07-30
tags:

• Algorithm
• DFS

---

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

문제 요약

유저들의 아이디와 제재된 유저의 아이디가 주어진다.
제재된 유저의 아이디 중 일부는 ''로 표기하였으며, ''을 제외한 아이디가 동일하면 제재 대상으로 볼 수 있다.
하나의 제재된 유저의 아이디는 기존 유저들의 아이디 중 여러개와 매칭이 될 수 있다.
제재가 가능한 경우의 수를 return한다.

문제 풀이

삽질을 너무도 많이 반복한 문제이다.
DFS 방식을 이용하여 모든 제재된 아이디가 유저에게 할당될 경우, 경우의 수를 하나씩 늘렸다.


처음에는 비효율적인 알고리즘을 작성하였다.
우선 아이디 비교에서 string 및 char 연산이 이루어지기에 이 부분에서 효율성이 조금 안 좋다고 판단하였다.
제일 중요한 것은 모든 제재된 아이디가 ''로만 이루어질 때, 최대 8!의 경우를 모두 검사하였다. 하지만 이는 1개의 경우의 수의 조합일 뿐이다.
이로 인해 위에서 말한 케이스의 경우 시간 초과가 발생하였으며, 이를 해결하기 위하여 두 부분을 수정하였다.


우선 아이디는 최대 8글자이며, 소문자와 숫자 혹은 ''로 이루어질 수 있다. 최대 36가지의 경우의 수가 나오며, 이는 6bits로 구별할 수 있다.
최대 48bits를 통해 아이디를 수로 바꿀 수 있기에, 각 아이디를 전부 수로 바꾸는 작업을 하였다.
이를 통해 string 및 char 연산을 줄이고 비트 연산을 통해 성능을 일부 챙겼다.

그리고 제일 문제가 되는 조합의 경우, 비슷한 문제를 겪었기에 이 때 사용하였던 방법을 사용하였다.
덕분에 최악의 경우 8!를 검사해야 하던 이전과는 다르게, 최대 70가지의 경우의 수만 확인하면 되는 알고리즘으로 수정하였다.

위 두 가지의 수정 사항 덕분에 시간 초과, 몇십 ms가 걸리던 수행 시간을 최대 약 0.06ms까지 줄일 수 있었다.

프로그램

#include <string>
#include <vector>
#include <algorithm>

using std :: string ;
using std :: vector ;

int iUserSize ;

bool bCanBanUser ( long long llUser , long long llBan )
{
    while ( ( 0 != llUser ) && ( 0 != llBan ) )
    {
        int iUserValue = llUser & 63 ;
        int iBanValue = llBan & 63 ;

        if ( ( 63 != iBanValue ) && ( iUserValue != iBanValue ) )
            break ;

        llUser >>= 6 ;
        llBan >>= 6 ;
    }

    if ( ( 0 != llUser ) || ( 0 != llBan ) )
        return false ;

    return true ;
}

bool bIsConfigPossible ( long long * llpUser , long long * llpBan , vector < bool > & vUserIsUsed , int iBanCount , int iMaxBan )
{
    if ( iBanCount == iMaxBan )                // If all user is banned
        return true ;

    for ( int i = 0 ; i < iUserSize ; ++i )
    {
        if ( vUserIsUsed [ i ] )
            continue ;

        long long llUser = llpUser [ i ] ;

        if ( bCanBanUser ( llUser , llpBan [ iBanCount ] ) )        // Can ban this user
        {
            vUserIsUsed [ i ] = true ;
            if ( bIsConfigPossible ( llpUser , llpBan , vUserIsUsed , iBanCount + 1 , iMaxBan ) )
            {
                vUserIsUsed [ i ] = false ;

                return true ;
            }
            vUserIsUsed [ i ] = false ;
        }
    }

    return false ;
}

int iGetCharToInt ( char cChar )        // Change alphabet,number -> 1~36 and 63. 1~26 alphabet, 27~35 number, 63 *
{
    if ( '*' == cChar )
        return 63 ;
    if ( ( 'a' <= cChar) && ( cChar <= 'z' ) )
        return cChar - 'a' + 1 ;
    else
        return cChar - '0' + 27 ;
}

int solution ( vector < string > user_id , vector < string > banned_id )
{
    int answer = 0 ;
    iUserSize = user_id.size () ;
    int iBannedUserSize = banned_id.size () ;
    vector < long long > vUserList ;
    vector < long long > vBanList ;



    for ( int i = 0 ; i < iUserSize ; ++i )                // Change user_id to long long
    {
        int iStringSize = user_id [ i ].size () ;
        const char * cpString = user_id [ i ].data () ;
        long long llValue = 0 ;

        for ( int j = 0 ; j < iStringSize ; ++j )
        {
            llValue <<= 6 ;
            llValue += iGetCharToInt ( * cpString ++ ) ;
        }

        vUserList.emplace_back ( llValue ) ;
    }
    for ( int i = 0 ; i < iBannedUserSize ; ++i )        // Change banned_id to long long
    {
        int iStringSize = banned_id [ i ].size () ;
        const char * cpString = banned_id [ i ].data () ;
        long long llValue = 0 ;

        for ( int j = 0 ; j < iStringSize ; ++j )
        {
            llValue <<= 6 ;
            llValue += iGetCharToInt ( * cpString ++ ) ;
        }

        vBanList.emplace_back ( llValue ) ;
    }


    vector < bool > vUserIsUsed ( iUserSize , true ) ;
    std :: fill ( vUserIsUsed.begin () , vUserIsUsed.begin () + iBannedUserSize , false ) ;

    do
    {
        if ( bIsConfigPossible ( vUserList.data () , vBanList.data () , vUserIsUsed , 0 , iBannedUserSize ) )
            ++ answer ;
    } while ( std :: next_permutation ( vUserIsUsed.begin () , vUserIsUsed.end () ) ) ;


    return answer ;
}