프로그래머스 - 신고 결과 받기 / C++

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

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

 

 

문제 풀이

게시판 불량 이용자를 신고하고 처리 결과를 메일로 받을 수 있는 시스템을 개발하려 한다.

한 유저를 여러 번 신고할 수도 있지만, 동일 유저에 대한 신고 횟수는 1회로 처리된다.

k번 이상 신고된 유저는 게시판 이용이 정지되며, 해당 유저를 신고한 모든 유저에게 정지 사실을 메일로 발송한다.

 

입출력은 모든 회원의 id가 존재하는 id_list 배열, ["muzi", "frodo", "apeach", "neo"] 형태

신고 목록을 보여주는 report 배열 ["muzi frodo", "apeach frodo", ... ] 형태

정지 기준 신고 횟수인 k가 주어지며 출력값은 [2, 1, 1, 0]과 같이 몇 개의 메일을 받는지 출력한다.

즉, muzi는 2개, frodo는 1개, apeach는 1개, neo는 0개의 메일을 받는다는 뜻이다.

 

문제 설명을 보고 내가 떠올린 순서이다.

1. report 배열을 for문으로 돌며 신고자와 신고 당한 사람을 split 해야겠다.

2. 결과가 결국 id_list의 인덱스를 ++하는 형태이기 때문에 신고자/피신고자를 인덱스로 기록하고 같은 신고자/피신고자 쌍은 1회로 기록되므로 중복 값이 없는 set을 써야겠다.

3. k회 이상 신고당한 사람을 찾아야하므로 신고당한 횟수를 기록하는 int형 reported 배열이 필요하겠다.

4. k회 이상 신고당한 사람을 신고한 모든 인덱스에 ++해주면 되겠다.

 

소스 코드

#include <bits/stdc++.h>
using namespace std;

vector<int> solution(vector<string> id_list, vector<string> report, int k) {
    vector<int> answer;
    vector<int> reported;
    set<pair<int, int> > reportPair;
    
    for(int i=0; i<id_list.size(); i++){
        reported.push_back(0);
        answer.push_back(0);
    }
    
    for(int i=0; i<report.size(); i++){
        string tmp;
        vector<string> ID;
        int a = 0, b = 0;
        
        istringstream iss(report[i]);
        while(getline(iss, tmp, ' ')){
            ID.push_back(tmp);
        }//ID[0]는 신고자, ID[1]은 신고 당한 사람
        
        for(int j=0; j<id_list.size(); j++){
            if(id_list[j] == ID[0]) a = j;
            if(id_list[j] == ID[1]) b = j;
        }
        
        reportPair.insert(make_pair(a, b));
    }
    
    for(auto it=reportPair.begin(); it != reportPair.end(); ++it){
        reported[it->second]++;
    }
    
    for(int i=0; i<reported.size(); i++){
        if(reported[i] >= k){
            for(auto it : reportPair){
                if(it.second == i){
                    answer[it.first]++;
                }
            }
        }
    }
    
    return answer;
}

 

시행 착오

3번 테스트 케이스에서 시간 초과가 났다.

기존 코드는 아래와 같은 for문을 썼는데 범위 기반 for문으로 대체하니까 시간 초과가 풀렸다. 

for(int i=0; i<reported.size(); i++){
    if(reported[i] >= k){
        for(auto it=reportPair.begin(); it != reportPair.end(); ++it){
            if(it.second == i){
                answer[it->first]++;
            }
        }
    }
}

 

개인적인 생각과 아래의 글을 참고해보면 범위 연산 for문의 it는 원소에 이미 접근된 상태이고 begin ~ end를 순회하는 for문은 포인터로 접근하는 시간이 포함되어 시간 차이가 나는 것 같다.

https://m.blog.naver.com/PostView.naver?isHttpsRedirect=true&blogId=4roring&logNo=221337048963 

STL vector의 원소를 순회하는 다양한 방법의 속도