프로그래머스 [연습문제 / 신고 결과 받기](C++) -yes6686- 티스토리

프로그래머스 문제 풀이: 92334 신고 결과 받기

---

문제 링크: https://school.programmers.co.kr/learn/courses/30/lessons/92334

문제 설명:

게시판 신고 시스템을 구현하는 문제입니다. 유저들이 다른 유저를 신고할 수 있으며, 동일 유저에 대한 중복 신고는 1회로 처리됩니다. k번 이상 신고당한 유저는 이용이 정지되며, 해당 유저를 신고한 모든 유저에게 메일이 발송됩니다. 각 유저가 받은 메일 횟수를 id_list 순서대로 반환하는 해시맵과 집합 자료구조를 활용한 구현 문제입니다.

---

문제 해결 코드

#include <string>
#include <vector>
#include <map>
#include <set>
#include <sstream>
using namespace std;

vector<int> solution(vector<string> id_list, vector<string> report, int k) {
    vector<int> answer;
    
    // 중복 신고 제거를 위한 set
    set<string> uniqueReports(report.begin(), report.end());
    
    // 각 유저가 신고당한 횟수
    map<string, int> reportCount;
    
    // 각 유저가 신고한 유저 목록 (신고자 → 피신고자 리스트)
    map<string, vector<string>> reportHistory;
    
    // 중복 제거된 신고 내역 처리
    for(const string& rep : uniqueReports) {
        stringstream ss(rep);
        string reporter, reported;
        ss >> reporter >> reported;
        
        // 신고당한 횟수 증가
        reportCount[reported]++;
        
        // 신고 이력 저장
        reportHistory[reporter].push_back(reported);
    }
    
    // k번 이상 신고당한 유저 목록 (정지된 유저)
    set<string> bannedUsers;
    for(const auto& entry : reportCount) {
        if(entry.second >= k) {
            bannedUsers.insert(entry.first);
        }
    }
    
    // 각 유저가 받을 메일 횟수 계산
    for(const string& user : id_list) {
        int mailCount = 0;
        
        // 해당 유저가 신고한 유저들 확인
        if(reportHistory.find(user) != reportHistory.end()) {
            for(const string& reported : reportHistory[user]) {
                // 신고한 유저가 정지되었다면 메일 발송
                if(bannedUsers.find(reported) != bannedUsers.end()) {
                    mailCount++;
                }
            }
        }
        
        answer.push_back(mailCount);
    }
    
    return answer;
}

---

코드 설명

• 핵심 알고리즘: 해시맵과 집합 자료구조를 활용한 정보 관리입니다. set으로 중복 신고를 자동 제거하고, map으로 신고 횟수와 이력을 추적합니다. 먼저 모든 신고를 처리하여 각 유저의 신고당한 횟수를 계산하고, k번 이상 신고당한 유저를 정지 목록에 추가합니다. 그 후 각 유저가 신고한 사람 중 정지된 유저의 수를 세어 메일 횟수를 계산합니다.
• 구현 세부사항:
  • set으로 report 배열의 중복을 자동 제거합니다.
  • stringstream을 사용하여 "신고자 피신고자" 형식의 문자열을 간편하게 파싱합니다.
  • reportCount 맵으로 각 유저가 신고당한 총 횟수를 추적합니다.
  • reportHistory 맵으로 각 유저가 누구를 신고했는지 기록합니다.
  • bannedUsers 집합에 k번 이상 신고당한 유저를 저장합니다.
  • id_list 순서대로 각 유저가 신고한 사람 중 정지된 유저 수를 계산합니다.
• 시간/공간 복잡도: 시간 복잡도는 O(n + m)입니다. 여기서 n은 report 배열의 길이, m은 id_list 길이입니다. set 생성에 O(n log n), 신고 처리에 O(n), 결과 계산에 O(m ⋅ r)이 소요됩니다(r은 각 유저가 신고한 평균 유저 수). 공간 복잡도는 O(n + m)으로 맵과 집합에 저장되는 데이터의 총량에 비례합니다.

---

실행 예시

테스트 케이스:

입력: id_list = ["muzi", "frodo", "apeach", "neo"], report = ["muzi frodo", "apeach frodo", "frodo neo", "muzi neo", "apeach muzi"], k = 2

실행 과정:

• 중복 제거 후 신고 내역: ["muzi frodo", "apeach frodo", "frodo neo", "muzi neo", "apeach muzi"]
• 신고당한 횟수:
  • frodo: 2회 (muzi, apeach)
  • neo: 2회 (frodo, muzi)
  • muzi: 1회 (apeach)
• 정지된 유저 (k=2): frodo, neo
• 메일 발송:
  • muzi: frodo, neo 신고 → 둘 다 정지 → 2회
  • frodo: neo 신고 → neo 정지 → 1회
  • apeach: frodo, muzi 신고 → frodo만 정지 → 1회
  • neo: 신고 안 함 → 0회

출력: [2, 1, 1, 0]

---

결과

해시맵과 집합 자료구조를 효과적으로 활용하여 신고 시스템을 구현했습니다. 원본 코드는 여러 맵을 사용하여 중복을 수동으로 체크했지만, 리팩토링된 코드는 set으로 중복을 자동 제거하고 stringstream으로 문자열 파싱을 간소화했습니다. reportHistory와 bannedUsers를 명확하게 구분하여 로직의 가독성을 크게 향상시켰으며, 각 단계의 목적이 명확하여 유지보수가 용이합니다.

다른 접근 방식이나 개선 사항이 있다면 댓글로 공유 부탁드립니다!