Programmers - 순위 검색

---

title: Programmers - 순위 검색
date: 2022-07-09
tags:

• Algorithm
• Bitmasking

---

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

문제 요약

지원자들은 5가지 정보를 가지고 있다. 조건 n개가 주어졌을 때, 각 조건을 통과하는 지원자가 몇명인지 vector에 넣어 return한다.

문제 풀이

이건 난이도 설정이 잘못되었다. 최소 Level 3 이상이다.
조건이 문자열들이며, 한두개가 아니었기에 바로 비트마스킹이 떠올랐다.
OneHotEncoder와 비슷하게 각 비트가 조건에 해당하는지를 알려주었다. 문자열 조건은 총 9개로, 9비트를 이용하였다.
점수는 100k까지로, 17비트면 충분하였지만 이는 비교를 해야하는 정보이기에 문자열 조건과 따로 나누었다.
문제는 지원자가 최대 50k, 조건은 100k이다. 무식하게 하나하나 비교하면 5B만큼 비교해야 하는 것이다.
효율성에서 계속하여 실패하였으며, 조건마다 확인해야 하므로 100k는 default로 깔고 들어가야 했다.
이를 해결하기 위하여 unordered_map을 사용하여 50k 순회를 24회 순회로 변경하였다.

비트마스킹 값을 Key에, 점수를 가지는 vector를 Value로 사용하였다.
unordered_map에 존재하는 모든 Key를 비교하며 문자열 조건을 통과할 때, lower_bound를 이용하여 특정 점수 이상의 인원수를 바로 가져왔다.
lower_bound는 동작이 매우 간단하다.

std :: lower_bound ( A , B , Value )

A~B 공간에서 Value보다 크거나 같은 값이 처음으로 몇 번째에 나오는지 알려준다.
이를 이용하여 모든 지원자를 순회하지 않고, 조건에 알맞을 경우 특정 점수가 넘는 지원자의 인원수를 바로 알 수 있었다.

효율성 테스트에서 164, 165, 596, 566ms의 결과를 확인할 수 있었다.
성능 측면에서 개선할 부분이 여전히 많이 있다는 것을 알 수 있다.
아마도 비트마스킹과 unordered_map의 Key 설정 부분을 개선하면 훨씬 좋은 성능을 보일 것이라 생각한다.

문제 풀이 완료 후, 다른 분들은 istringstream 을 이용하여 문자열을 파싱하는 것을 확인하였다.
istringstream은 stringstream과 비슷하다. 공백과 \n 문자를 제외하여 파싱을 진행한다.
이러한 문제처럼 delimeter가 공백이라면 stringstream을 사용하는 것이 더 좋은 방법일 수도 있다.

프로그램

#include <string>
#include <vector>
#include <utility>
#include <cstring>
#include <algorithm>
#include <unordered_map>

using std :: vector ;
using std :: string ;
using std :: pair ;
using std :: unordered_map ;

pair < int , int > getCondition ( string strCondition )
{
    int iApplyInfo = 0 ;            // Bit masking. Each details at 1 bit. All 9 bits
    char * cpTemp = strtok ( & strCondition [ 0 ] , " " ) ;



    if ( 'c' == cpTemp [ 0 ] )
        iApplyInfo |= 0b100000000 ;
    else if ( 'j' == cpTemp [ 0 ] )
        iApplyInfo |= 0b010000000 ;
    else if ( 'p' == cpTemp [ 0 ] )
        iApplyInfo |= 0b001000000 ;
    else
        iApplyInfo |= 0b111000000 ;

    cpTemp = strtok ( NULL , " " ) ;
    if ( 'a' == cpTemp [ 0 ] )
        cpTemp = strtok ( NULL , " " ) ;

    if ( 'b' == cpTemp [ 0 ] )
        iApplyInfo |= 0b000100000 ;
    else if ( 'f' == cpTemp [ 0 ] )
        iApplyInfo |= 0b000010000 ;
    else
        iApplyInfo |= 0b000110000 ;

    cpTemp = strtok ( NULL , " " ) ;
    if ( 'a' == cpTemp [ 0 ] )
        cpTemp = strtok ( NULL , " " ) ;

    if ( 'j' == cpTemp [ 0 ] )
        iApplyInfo |= 0b000001000 ;
    else if ( 's' == cpTemp [ 0 ] )
        iApplyInfo |= 0b000000100 ;
    else
        iApplyInfo |= 0b000001100 ;

    cpTemp = strtok ( NULL , " " ) ;
    if ( 'a' == cpTemp [ 0 ] )
        cpTemp = strtok ( NULL , " " ) ;

    if ( 'c' == cpTemp [ 0 ] )
        iApplyInfo |= 0b000000010 ;
    else if ( 'p' == cpTemp [ 0 ] )
        iApplyInfo |= 0b000000001 ;
    else
        iApplyInfo |= 0b000000011 ;

    cpTemp = strtok ( NULL , " " ) ;

    return std :: make_pair ( iApplyInfo , atoi ( cpTemp ) ) ;
}

vector < int > solution ( vector < string > info , vector < string > query )
{
    vector < int > answer ;
    int iInfoLen = info.size () ;
    int iQueryLen = query.size () ;
    unordered_map < int , vector < int > > umApply ;



    answer.resize ( iQueryLen ) ;
    for ( int i = 0 ; i < iInfoLen ; ++i )
    {
        pair < int , int > tempPair = getCondition ( info [ i ] ) ;

        umApply [ tempPair.first ].emplace_back ( tempPair.second ) ;
    }

    for ( auto iter = umApply.begin () ; iter != umApply.end () ; ++ iter )
    {
        std :: sort ( iter -> second.begin () , iter -> second.end () ) ;
    }

    for ( int i = 0 ; i < iQueryLen ; ++i )
    {
        pair < int , int > conditionPair = getCondition ( query [ i ] ) ;

        for ( auto iter = umApply.begin () ; iter != umApply.end () ; ++ iter )
        {
            if ( iter -> first != ( iter -> first & conditionPair.first ) )
                continue ;

            vector < int > vTemp = umApply [ iter -> first ] ;

            if ( ! vTemp.empty () )
            {
                answer [ i ] += ( vTemp.size () - ( std :: lower_bound ( vTemp.begin () , vTemp.end () , conditionPair.second ) - vTemp.begin () ) ) ;
            }
        }
    }


    return answer ;
}