[프로그래머스] Lv.1 신고 결과 받기 c++

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

프로그래머스

 

2022 KAKAO BLIND RECRUITMENT에 나온 문제입니다. 

무지는 게시판 불량 이용자를 신고하고 정지 결과를 메일로 발송하는 시스템을 개발하려 합니다. 각 유저는 한 번에 한 명의 유저를 신고할 수 있으며, 중복 신고는 1회로 처리됩니다. 한 유저가 k번 이상 신고되면 게시판 이용이 정지되고, 신고자들에게 정지 사실을 메일로 발송합니다. 모든 신고 내역은 취합 후 한꺼번에 처리됩니다.

예를 들어, 유저 목록이 ["muzi", "frodo", "apeach", "neo"]이고 k=2k = 2k=2인 경우, 신고 내역에 따라 정지 및 메일 발송이 결정됩니다.

 

풀이 방법

좀 복잡하게 풀었습니다...

이차원 배열을 만들어 중복 신고를 없애고, unordered_map 자료구조를 사용하여 신고자는 key로, 신고자의 인덱스 위치와 신고된 숫자를 저장했습니다. 이후 map을 탐색하여 신고 횟수가 k번 이상인 경우, 미리 선언해 둔 answer 배열에 해당 신고자의 인덱스 위치를 찾아 +1 해줬습니다.

한 번에 풀어서 기분은 좋았지만, 다른 풀이 방식을 보니 시간 복잡도를 훨씬 줄일 수 있을 것 같습니다...

사실, 자료구조를 아래처럼 변경하면 시간 복잡도를 더 효과적으로 줄일 수 있습니다:

unordered_map<string, vector<string>> user_reports;​

이러면 각 신고자별로 신고한 사용자 리스트를 저장할 수 있고, 신고 중복 확인도 더 간단하게 처리할 수 있습니다.

이후, 최종 계산에서 신고된 사용자 리스트만 순회하면 되기 때문에 코드가 더 간단해지고 효율적으로 동작합니다.

 

풀이 코드

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

using namespace std;

bool report_list[1000][1000];
string user, reported_user;
int user_index, reported_user_index;
unordered_map<string,pair<int,int>> map;
vector<int> solution(vector<string> id_list, vector<string> report, int k) {
    vector<int> answer(id_list.size());
    for(int i=0; i<id_list.size(); i++) map[id_list[i]]={i,0};
    for(string s : report){
        stringstream ss(s);
        ss >> user >> reported_user;
        user_index = map[user].first;
        reported_user_index = map[reported_user].first;
        
        if(!report_list[reported_user_index][user_index]){
            report_list[reported_user_index][user_index] = true;
            map[reported_user].second++;
        }
    }
    
    for(auto& iter : map){
        if(iter.second.second >= k){
            for(int i=0; i<id_list.size(); i++){
                if(report_list[iter.second.first][i]) answer[i]++;
            }
        }
    }
    return answer;
}