[프로그래머스] 신고 결과 받기(feat. unordered_map vs. map)

문제

https://programmers.co.kr/learn/courses/30/lessons/92334?language=cpp 

코딩테스트 연습 - 신고 결과 받기

사실 풀자마자 어떻게 푸는지 감은 왔으나, 지나치게 오랜만에 문제를 접한 탓에 메소드들이 생각이 잘 안 나서 살짝 헤맸다..

그래도 풀자마자 통과할 수 있었다...(다행)

 

이 문제는 특별한 자료구조나 알고리즘이 필요한 것이 아니라 그냥 요구사항을 제대로 이해해야하는 게 관건이다.

특히 신고한 유저 - 신고 당한 유저의 관계에 관심을 가져야 한다.

왜냐하면 중복된 신고관계가 여러 개 존재할 수 있기 때문이다.

따라서 유저별로 신고한 아이디를 기록하기 위해 set를 설정하였다.(set은 중복을 허용하지 않기 때문)

이를 통해 중복을 제거하고 유저가 신고한 ID 리스트를 얻을 수 있다.

그런데 반대로 신고당한 유저도 본인을 신고한 유저를 기록해야 한다.

그래야 중복되지 않은 총 신고 횟수를 알 수 있기 때문이다.

이 부분만 이해하면 아래와 같이 간단하게 문제를 풀어낼 수 있다.

#include <string>
#include <vector>
#include <map>
#include <set>
#include <sstream>
using namespace std;
// 각 유저별로 신고당한 횟수 기록
map<string, set<string>> blacklist1;
// 각 유저별로 신고한 아이디 기록
map<string, set<string>> blacklist2;
vector<int> solution(vector<string> id_list, vector<string> report, int k) {
    vector<int> answer;
    istringstream iss;
    string a, b;
    for(auto r : report) {
        iss.str(r);
        iss.seekg(0);
        // a가 b를 신고함
        iss >> a >> b;
        blacklist1[b].insert(a);
        blacklist2[a].insert(b);
    }
    
    for(auto id : id_list) {
        int num = 0;
        for(auto s : blacklist2[id]) {
            if(blacklist1[s].size() >= k) {
                num++;
            }
        }
        answer.push_back(num);
    }
    return answer;
}

💡map vs. unordered_map

우선 둘의 가장 두드러지는 차이는 정렬 유무다.

이는 구현방식이 다르기 때문이다.

map은 균형 이진 트리(Red Black Tree)로 구현되는 반면, unordered_map은 Hash Table로 구현된다.

이로 인해 map은 자동으로 Key 값에 따라 정렬되는 반면, unordred_map은 정렬되지 않는다.

 

Red Black Tree는 검색 속도가 빠른 BST(Binary Search Tree)에 Self-Balancing 기능을 추가한 것이다.

이를 통해 탐색 시 O(logN) 수준을 최대한 보장한다.

반면 Hash Table은 해시값을 이용하기 때문에 거의 O(1) 수준의 시간 복잡도를 가진다.

데이터의 크기를 N이라고 한다면, N이 작을 때는 map, 클 때는 unordered_map이 유리하다.

왜냐하면 N이 클수록 map은 여러 노드를 방문해야하기 때문에 캐시 미스가 늘어나서 효율이 떨어지기 때문이다.

특히 map은 문자열 키를 사용하는 경우에는 정수 키를 사용하는 경우에 비해 더 큰 N까지 탐색 성능 우위를 가진다. 왜냐하면 문자열 비교에는 적은 비교 횟수가 필요하기 때문이다.

하지만 만약 element의 수가 많은 경우에는 Hash Collison이 발생하는 경우도 있을 수 있기 때문에 주의해야 한다.

 

참고

http://veblush.github.io/ko/posts/map-vs-unorderedmap-for-string-key/

문자열 키의 map, unordered_map 성능 비교

 

 

💡sstream

지나치게 오랜만에 C++을 활용하는 탓에 문자열을 파싱하는 방법도 가물가물했다.

sstream 헤더에는 주로 istringstream, ostringstream, stringstream이 있다.

그 중 istringstream은 공백을 기준으로 문자열을 파싱하고, 변수 형식에 맞게 입력하기에 용이하다.