Lv1_[신고결과 받기, C++] 알고리즘 정리 - 프로그래머스

문제 내용, 조건, 예시는 프로그래머스 사이트 참조

---

내가 신고한 ID가 정지가 되었을 때, 나에게 결과를 받는 형태로 구성해주기 위해 map을 활용해서 key, value를 설정해줬다.

· map<유저ID, 나를 신고한 유저들 ID> UserID;
· map<string, vector<string>> UserID;
Key에 유저ID를 넣고 Value에 나를 신고한 유저들 ID를 세팅해줬다.
value의 vector크기는 k(정지 기준이 되는 신고 횟수)랑 비교하면 되고, vector크기가 k와 같거나 크면 value에 저장되어 있는 유저들에게 신고 결과를 통보해주면 된다.

 

Value(vector) 크기가 k(2) 이상인 유저는 "frodo, neo"가 되고, "muzi"에게 2번, "apreach"에게 1번, "frodo"에게 1번 통보해주면 된다.

통보하는 횟수는
· map<통보유저ID, 통보 횟수> notified_Count;
· map<string, unsigned int> notified_Count;
에 넣어서 저장 후 결과로 반환시켜주게 된다.

여기서 빼먹지 말고 해줘야할 내용은 조건 중에
"한 유저를 여러 번 신고할 수도 있지만, 동일한 유저에 대한 신고 횟수는 1회로 처리됩니다."가 있기 때문에 중복된 신고 내역은 미리 제거를 해줘야 한다.

// 중복된 신고 제거
sort(report.begin(), report.end());
report.erase(unique(report.begin(), report.end()), report.end());

위 코드는 vector에서 중복된 내용을 삭제하는 방법이다.
(※위의 방법이 아니고 set<>을 활용해서 중복 값을 제거하는 방법도 있으니 참고하길 바랍니다. set을 쓴다면 나를 신고한 유저들 ID(vecter<string>이 set<string>으로 변경해서 사용해야 함.)

 

 

#include <string>
#include <vector>
#include <map>
#include <sstream>
#include <algorithm>
 
vector<int> solution(vector<string> id_list, vector<string> report, int k) {
    vector<int> answer;
 
    // 통보 받는 유저, 횟수
    map<string, unsigned int> notified_Count;
    // 유저, 나를 신고한 유저들
    map<string, vector<string>> UserID;
 
    // 중복된 신고 제거
    sort(report.begin(), report.end());
    report.erase(unique(report.begin(), report.end()), report.end());
 
    // 나를 신고한 유저들 저장
    for (auto str : report) {
        istringstream ss(str);
        string stringBuffer;
        vector<string> x;
        while (getline(ss, stringBuffer, ' ')){
            x.push_back(stringBuffer);
        }
        string reporter = x[0];
        string reported_User = x[1];
 
        UserID[reported_User].push_back(reporter);
    }
 
    // 신고 횟수 비교
    map<string, vector<string>>::iterator iter;
    for(iter = UserID.begin(); iter != UserID.end(); iter++) {
        vector<string> reported_User = iter->second;
        unsigned int reported_count = reported_User.size();
        // 누적 신고가 k번 이상일 때
        if(reported_count >= k) {
            for(auto ID : reported_User) {
                notified_Count[ID] += 1;
            }
        }
    }
 
    // 통보하기
    for(auto ID : id_list) {
        if(notified_Count.find(ID) != notified_Count.end()) {
            answer.push_back(notified_Count[ID]);
        } else {
            answer.push_back(0);
        }
    }
 
    return answer;
}

 

제한시간 안내
'정확성 테스트 : 10초'

가장 오래 걸린 것이 0.286초로 테스트 시간은 잘 나온 것 같다

 

↓↓↓↓↓↓ 유익했다면 하트 뿅 ♥ ↓↓↓↓↓↓