[Programmers] 신고 결과 받기(C++)

본 포스팅은 wakekang님의 티스토리 게시글을 참고하였습니다.

---

[프로그래머스] 신고 결과 받기 문제 링크

본 문제에선 세 가지 중요한 개념을 사용하였다. 바로 unordered_map, set, 그리고 stringstream이다. 각각 <unordered_map>, <set>, <sstream> 헤더를 포함하여 사용할 수 있다.

위 개념들을 사용한 이유는 다음과 같다.

• unordered_map : idx_map과 report_map이라는 두 개의 맵을 사용한다. idx_map은 기본적으로 주어지는 유저 목록인 id_list를 빠르게 접근하기 위함, report_map은 신고자 목록을 저장하기 위함이다.
  정렬이 필요가 없고, Hash를 이용하는 unordered_map의 특성상 데이터를 목록에서 찾는 작업을 상수 시간($O(1)$)에 해결할 수 있기 때문에 해당 자료구조를 사용한다.
• set : report_map의 value 자료형을 vector와 같은 배열 컨테이너로 사용할 수도 있겠지만, 동일한 유저에 대한 신고 횟수는 1회로 처리 즉, 중복을 허용하지 않는다는 특성을 고려하여 set 자료구조를 사용한다.
• stringstream : 신고 내용을 가리키는 report 객체가 "muzi frodo"처럼 신고자와 피신고자를 한 문자열에 묶여 있기 때문에 이를 간편하게 파싱하는 용도로 사용하는 클래스이다.

바로 코드를 살펴보자.

#include <string>
#include <vector>
#include <unordered_map>
#include <set>
#include <sstream>

using namespace std;

vector<int> solution(vector<string> id_list, vector<string> report, int k) {
    vector<int> answer(id_list.size(), 0); // 반드시 초기화를 해준다.
    
    unordered_map<string, int> idx_map; // id_list라는 벡터 전체를 탐색하지 않고 빠르게 탐색
    for(int index = 0; index < id_list.size(); index++){
        idx_map[id_list[index]] = index;	// 유저의 아이디를 key로 넣고 
    }										// id_list에서의 인덱스를 value로 저장한다. 
    
    unordered_map<string, set<string>> report_map; // 실제 신고 내용을 저장하는 맵
    
    stringstream reporting_stream; // 신고 내용이 담긴 string을 파싱하기 위한 stringstream
    for(auto reporting_str : report){
        reporting_stream.str(reporting_str); // stream의 값을 원하는 string으로 바꾼다.
        
        string reporter, reported;
        reporting_stream >> reporter >> reported; // 공백에 따라 문자열 파싱이 가능하다.
        
        report_map[reported].insert(reporter);
        
        reporting_stream.clear();   // clear를 해줘야 새로운 문자열 str을 받았을 때
    }								// 문자열의 첫 위치부터 읽어낼 수 있다.
    
    for(auto it : report_map){
        if(it.second.size() >= k){ // 특정 유저에 대한 신고자가 k명 이상일 때
            for(auto reporter_list : it.second){ // it.second : 신고자 목록(set<string>)
                int idx = idx_map[reporter_list]; // 피신고자의 인덱스를 idx_map에서 찾음
                answer[idx]++;
            }
        }
    }
    
    return answer;
}