[C++] Programmers Lv. 1 "신고 결과 받기"

🔵 문제 링크

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

프로그래머스

 

🔵 문제 접근

문제를 정리해 보면 다음과 같다.

• 유저는 여러 명을 신고할 수 있다.
• 한 유저가 같은 유저를 여러번 신고한다면 그건 1번으로 처리한다.
• 신고 횟수가 k 이상 누적되면 그 사람을 신고한 사람에게 정지 메일이 발송됨.

여기서 (신고당한 유저 - 신고한 사람) map 구조를 사용해야 한다는 걸 떠올렸다.

신고 당한 횟수가 얼마나 누적되었는지가 답에 영향을 미치기 때문에, 신고당한 유저를 key값으로 설정했다.

value는 한 유저가 같은 유저를 여러번 신고할 수 없기 때문에, 중복 신고 방지가 가능한 set을 선택하였다.

 

답은 map을 돌면서 value.size()가 k 이상임을 확인하여 정지 메일 발송을 처리하면 된다.

 

🔵 전체 코드

#include <string>
#include <vector>
#include <sstream>
#include <unordered_set>
#include <unordered_map>
using namespace std;

// 유저 신고 -> (여러 명 신고 가능)
// 한 유저가 같은 유저를 계속 신고하면 그건 1번 처리
// 신고 횟수가 k가 되면 유저 당 정지 메일 발송

// 신고 당한 사람 - 신고한 사람 set(중복 신고 방지)? 
// set size가 k를 넘기면 id_list에 담긴 id(신고한 사람) 순서대로 결과 메일 수 담기

vector<int> solution(vector<string> id_list, vector<string> report, int k) 
{
    vector<int> answer(id_list.size());
    unordered_map<string, int> userTable;
    unordered_map<string, unordered_set<string>> reportTable;

    // 이름으로 id 값을 바로 찾기 위해 hash 생성
    for (int i = 0; i < id_list.size(); i++)
        userTable[id_list[i]] = i;

    // 각 id 별로 신고당한 횟수와 신고한 사람(set으로 중복 x) 누적
    for (int i = 0; i < report.size(); i++)
    {
        // 공백으로 신고한 사람, 신고당한 사람 구분
        stringstream ss(report[i]);
        string reporter = "";
        string reportee = "";
        ss >> reporter >> reportee;

        reportTable[reportee].insert(reporter);
    }

    // 신고 횟수가 k 이상인 사람 구별 후 신고자에게 메일 전송
    for (const auto& pair : reportTable)
    {
        if (pair.second.size() >= k)
        {
            for (string name : pair.second)
            {
                int userId = userTable[name];
                answer[userId]++;
            }
        }
    }

    return answer;
}

 

🔵 시간 복잡도

첫 번째 for문에서 id_list는 최대 1000이므로 상수로 취급할 수 있다.

두 번째 for문에서 report의 최대 길이를 N이라 했을 때, 시간 복잡도는 O(N)이다. (unordered_set의 insert 연산은 평균적으로 O(1)이다.)

 

세 번째 for문이 중요한데, 이중 for문이지만 시간 복잡도는 O(N)이다.

reportTable을 순회하며 각 set의 길이만큼 순회하는 것이지만, 이는 결국 중복 신고를 제외한 report 배열의 길이와 같다.

즉, 최악의 경우(중복이 없을 경우) O(N = report 길이)인 것이다.

 

따라서 이 코드의 시간 복잡도는 O(N)이다.