[프로그래머스] 2021 Kakao Blind Recruitment - 순위 검색

풀이

풀이과정

문제를 처음 읽었을 때는 대단히 간단해보였다.
그냥 주어진 info 대로 정보들을 저장하고, 지원자가 각각의 query 조건을 만족하면 반환되는 result 배열의 값을 1 증가시켜주면 되는 간단한 로직이기 때문이다.

하지만.. "[본 문제는 정확성과 효율성 테스트 각각 점수가 있는 문제입니다.]" 가 문제였다.

일반적인 방식으로 모든 지원자들의 조건들을 검사하면 최악의 경우

$O(NQ)$

$50,000(info) *100,000(query) = 5,000,000,000$
즉 50억의 시간 복잡도가 나오게 된다.

vector<int> solution(vector<string> info, vector<string> query) {
    int infoNum = info.size();
    int queryNum = query.size();
    vector<vector<string>> afterInfo(infoNum, vector<string>(5));
    vector<vector<string>> afterQuery(queryNum, vector<string>(5));

    //afterInfo에 다시 정리하기
    for(int i=0; i<infoNum; ++i){
        for(int j=0; j<5; ++j){
            //공백 기준으로 나누기<<공부!!
            size_t pos = 0;
            size_t prev = 0;
            while ((pos = info[i].find(' ', prev)) != string::npos) {
                afterInfo[i][j] = info[i].substr(prev, pos - prev);
                prev = pos + 1;
                j++;
            }
            afterInfo[i][j] = info[i].substr(prev);
        }
    }
    //afterQuery에 다시 정리하기
    for(int i=0; i<queryNum; ++i){
        size_t start = 0;
        size_t pos;
        int cnt = 0;

        string temp = query[i];

        // " and " 기준으로 앞 3개만 자르기 (0~2)
        while (cnt < 3) {
            pos = temp.find(" and ", start);
            afterQuery[i][cnt] = temp.substr(start, pos - start);
            start = pos + 5; // " and " 길이
            cnt++;
        }
        // 마지막 2개 자르기 (3~4)
        pos = temp.find(' ', start);
        afterQuery[i][cnt] = temp.substr(start, pos - start);  
        afterQuery[i][cnt + 1] = temp.substr(pos + 1);         
    }

    //선별하기
    vector<int> result(queryNum, 0);
    for(int i=0; i<queryNum; ++i){
        for(int j=0; j<infoNum; ++j){
            // 모든 항목이 다 같을 때만 result[i]++
            bool match = true;
            for (int k = 0; k < 4; ++k) {
                // "-"이면 그냥 넘어감
                if (afterQuery[i][k]=="-") continue;
                if (afterQuery[i][k] != afterInfo[j][k]) {
                    match = false;
                    break;
                }
            }
            if (stoi(afterQuery[i][4]) > stoi(afterInfo[j][4])) continue; //점수조건
            if (match) result[i]++;
        }
    }
    
    return result;
}

이렇게 그냥 무지성으로 구현했더니 테스트 케이스는 모두 통과했지만 효율성 검사에서 모두 통과하지 못했다.

그래서 GPT의 도움을 조금 빌리면서.. 코드를 싹 갈아엎었다.

로직을 요약하자면 다음과 같다.

1. unordered_map에 해당 지원자를 조회 가능하게 하는 모든 key 조합을 생성한다. value로는 해당 지원자의 점수를 넣는다.
2. unordered_map의 점수들을 오름차순으로 정렬한다.
3. query의 조건을 만족하는 지원자 수를 세서 결과 배열에 넣는다.

위 로직의 시간복잡도는 $N*2^4 + Q*logN$이다.

• $N*2^4$ : info를 map에 정리하는데 걸리는 시간
• $Q*logN$ : query를 돌면서 이진탐색을 하는데 걸리는 시간

상수를 없애면 $Q*logN$이라고 볼 수 있고, 이는 기존의 시간복잡도였던 $QN$보다 작다.

그리고 worst case일 때의 수를 대입해보면,
$100,000 * log50000$는 약 1,500,000 정도로 충분히 짧은 시간이 소요된다.

이제 구체적으로 코드를 살펴보자.

void makeCases(string key, int depth, vector<string>& fields, unordered_map<string, vector<int>>& infoMap, int score) {
    //4개 조합이 모두 완성되면 push하고 종료
    if (depth == 4) {
        infoMap[key].push_back(score);
        return;
    }

    //원래 특성 쓰거나, '-' 쓰거나 두가지 경우를 재귀로
    makeCases(key + "-", depth + 1, fields, infoMap, score);
    makeCases(key + fields[depth], depth + 1, fields, infoMap, score);
}

하나의 지원자 정보에 대해서, 가능한 모든 key 조합을 만들어 infoMap에 push하는 함수이다.
재귀를 사용하여 해당 항목이 항목 그 자체인 경우와 '-'인 경우를 계속해서 구분하면서 조합을 생성한다.
4개의 항목이 있고 한 항목당 2개의 경우를 가질 수 있으므로, $2^4$개의 key값이 생기게 되는 것이다.

unordered_map<string, vector<int>> map;

map은 위와 같이 key 값을 string, value가 vector<int>으로 선언하여
위에서 만든 key 값 조합으로 access 할 수 있고, value에는 지원자들의 점수 배열이 들어가도록 한다.

    //점수 배열을 내림차순으로 정렬(오름차순??)
    for(auto& [key, arr] : map) {
        sort(arr.begin(), arr.end());
    }

위와 같이 각 value의 배열을 정렬해주어야 하는 이유는,
이진탐색을 하여 탐색에 필요한 시간을 단축하기 위함이다.

    //이제 query 조건을 만족하는 것들 개수 찾기
    for(int i=0; i<query.size(); ++i){
        istringstream ss(query[i]);
        vector<string> fields(8);
        //0, 2, 4, 6, 7(점수)에 값이 들어감
        ss >> fields[0] >> fields[1] >> fields[2] >> fields[3] >> fields[4] >> fields[5] >> fields[6] >> fields[7];
        string key = fields[0]+fields[2]+fields[4]+fields[6];

        vector<int> scores = map[key];
        auto it = lower_bound(scores.begin(), scores.end(), stoi(fields[7]));
        int cnt = scores.end() - it;
        result.push_back(cnt);
    }

마지막으로 query를 돌면서 조건을 만족하는 지원자 수를 찾아서 결과 배열에 넣어준다.
이때 lower_bound() 함수를 사용해 특정 값보다 커지기 시작하는 곳의 위치를 찾아서 해당 점수보다 큰 점수의 지원자들의 수를 계산한다.

최종 코드

void makeCases(string key, int depth, vector<string>& fields, unordered_map<string, vector<int>>& infoMap, int score) {
    //4개 조합이 모두 완성되면 push하고 종료
    if (depth == 4) {
        infoMap[key].push_back(score);
        return;
    }

    //원래 특성 쓰거나, '-' 쓰거나 두가지 경우를 재귀로
    makeCases(key + "-", depth + 1, fields, infoMap, score);
    makeCases(key + fields[depth], depth + 1, fields, infoMap, score);
}

vector<int> solution(vector<string> info, vector<string> query) {
    unordered_map<string, vector<int>> map;
    vector<int> result;
    
    for(string line : info){
        istringstream ss(line);
        vector<string> fields(5);
        ss >> fields[0] >> fields[1] >> fields[2] >> fields[3] >> fields[4];
        int score = stoi(fields[4]);
        fields.pop_back(); // key 조합 만드느데 쓰이면 안되기 때문에 제외
        makeCases("", 0, fields, map, score);
    }
    //이거 끝나면 이제 map 조합들이 완성된 상태이다.
    //점수 배열을 내림차순으로 정렬(오름차순??)
    for(auto& [key, arr] : map) {
        sort(arr.begin(), arr.end());
    }

    //이제 query 조건을 만족하는 것들 개수 찾기
    for(int i=0; i<query.size(); ++i){
        istringstream ss(query[i]);
        vector<string> fields(8);
        //0, 2, 4, 6, 7(점수)에 값이 들어감
        ss >> fields[0] >> fields[1] >> fields[2] >> fields[3] >> fields[4] >> fields[5] >> fields[6] >> fields[7];
        string key = fields[0]+fields[2]+fields[4]+fields[6];

        vector<int> scores = map[key];
        auto it = lower_bound(scores.begin(), scores.end(), stoi(fields[7]));
        int cnt = scores.end() - it;
        result.push_back(cnt);
    }

    return result;
}

새로 알게된 것

1. unordered_map

#include <unordered_map>

unordered_map <string, int> map;

빠른 검색/삽입/삭제가 가능한,
정렬되지 않은 해시 기반 딕셔너리이다.

위와 같이 선언한 경우에는 key는 string이 되고, value는 int가 된다. 즉 문자열로 정수값을 조회할 수 있게 되는 것이다.

기존의 일반 map과의 차이점은 다음과 같다.

항목	map	unordered_map
내부 구조	Red-Black Tree	해시 테이블
정렬됨?	✅ (key 기준)	❌
탐색 속도	O(log N)	O(1) 평균
사용 용도	순서가 중요할 때	속도가 중요할 때

즉 map보다 탐색 속도가 빠르고, 정렬되지 않은 딕셔너리이다.
해당 문제에서 정렬은 딕셔너리 값들 자체가 아니라 int 배열 내부에서 이루어져야 하기 때문에, 속도 향상을 위해 unordered_map을 사용하였다.

2. <sstream> 헤더

#include <sstream>

    for(string line : info){
        istringstream ss(line);
        vector<string> fields(5);
        ss >> fields[0] >> fields[1] >> fields[2] >> fields[3] >> fields[4];
	}

c++에서 <iostream> 헤더로 cin과 cout을 사용하는 것처럼,
<sstream>으로 문자열 입출력 흐름을 제어할 수 있다.

위의 예시에서는 line에 "java backend junior pizza 150"와 같은 값이 들어있고,
ss >> fields[0] >> fields[1] >> fields[2] >> fields[3] >> fields[4]; 에서 공백을 기준으로 배열에 문자열을 하나씩 입력받는 것이다.
즉 아래와 같이 배열이 채워지게 되는 것이다.

칸	값
fields[0]	java
fields[1]	backend
fields[2]	junior
fields[3]	pizza
fields[4]	150

istringstream은 입력 스트림이고, ostringstream은 출력 스트림으로 사용할 수 있다.

3. iterator 간 연산

        vector<int> scores = map[key];
        auto it = lower_bound(scores.begin(), scores.end(), stoi(fields[7]));
        int cnt = scores.end() - it;
        result.push_back(cnt);

두 번째 줄에서 lower_bound()는 iterator를 반환하기 때문에 처음에 it의 자료형은 iterator이나,
세 번째 줄에서 scores.end()와 빼기 연산을 하면서 정수형으로 변환되어 정수형 변수에 담을 수 있게 된다.
이처럼 반복자(iterator)끼리의 뺄셈 연산(iterator1 - iterator2)은 두 반복자 사이의 거리(칸 수)를 나타내는 정수형(difference_type) 값을 반환한다.

4. lower_bound() 함수

        vector<int> scores = map[key];
        auto it = lower_bound(scores.begin(), scores.end(), stoi(fields[7]));

정렬된 배열(컨테이너)에서 특정 값 이상($>=$)인 첫 번째 원소의 위치를 찾는 함수이다.

lower_bound(first, last, value)

• first : 탐색할 범위의 시작 위치
• last : 탐색할 범위의 끝 위치
• value : 찾고자 하는 값
• 반환값 : 만족하는 위치의 반복자(iterator)

비슷한 함수로 upper_bound()는 값을 초과($>$)하는 첫 위치를 반환한다.

주의할 점은, 꼭 '정렬된 배열'에서 사용해야 한다는 것이다!