[프로그래머스 Lv1] : 신고 결과 받기

문제 링크

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

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

유저들은 한 번에 한 명의 유저를 신고할 수 있다. K번 이상의 신고를 당한 사람은 이용 정지를 당한다.

정지당한 유저를 신고한 유저들에게 메일이 발송되는데, 각 유저별로 몇 통의 메일을 받았는지 출력하는 문제.

 

풀이

코딩테스트 문제는 백준과는 다르게 솔루션의 틀이 정해져있었다.

입력과 출력은 알아서 되고, 우리는 솔루션 함수만 작성하면 된다.

 

문제에 아래와 같은 조건이 주어져있다.

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

한 사람이 같은 사람을 여러 번 중복해서 신고할 수는 있지만, 유효하지는 않다는 뜻이다.

그래서 신고받은 내용이 담겨있는 report 벡터에서 unique를 이용해 중복을 제거해줬다.

• 중복을 제거하는 방법

1. 벡터를 정렬시켜준다. => sort(report.begin(), report.end());

2. 정렬시킨 벡터에서 unique가 리턴하는 인덱스 ~ 끝까지 삭제시킨다.

=> report.erase(unique(report.begin(), report.end()), report.end());

이렇게 하면 벡터내에 중복되는 인자들을 1개만 남기고 삭제할 수 있다.

• 신고 받은 내용 처리

신고내용은 문자열의 형태로 되어있다. "신고한 사람 신고당한 사람" 의 형식이다. 예를 들어 신고내용이 "Muzi Frodo" 면 무지가 프로도를 신고했다는 뜻이다. 문자열 내에서 띄워쓰기를 기준으로 신고한 사람과 신고당한 사람이 나누어진다. 그래서 띄워쓰기를 기준으로 문자열을 잘라줬다.

find 함수를 이용해서 띄워쓰기의 위치를 찾아낸다. string.find("",0) 이라고 하면 문자열에서 처음으로 띄워쓰기가 발견되는 인덱스를 리턴해준다.

그 인덱스를 기준으로 처음 ~ 스페이스바 앞, 스페이스바 뒤 ~ 끝까지 이렇게 문자열을 2개로 잘라주면 된다.

문자열을 자르는 건 substr() 함수를 이용했다. substr함수는 substr(시작인덱스, 자를 문자열의 길이) 이렇게 파라미터를 받는다.

그리고 count라는 배열을 만들어서 각 ID별로 총 몇번의 신고를 받았는지 셌다.

모든 신고내용을 처리한 후에 count 배열을 돌면서 값이 K이상인 ID는 정지를 당하게된다.

정지받은 해당 아이디를 누가 신고했는지를 알아야 메일을 발송해줄 수 있다. 그래서 Who_reported라는 벡터를 만들어서 

Who_reported[신고 받은 ID] = {신고한 ID} 이렇게 정보를 저장해두었다.

 

• 문자열인 아이디를 숫자인 인덱스로 변환

문자열 벡터인 id_list 에서 "Muzi"라는 사람의 ID가 몇 번째 인덱스에 있는 지 알아야 이 문제를 처리할 수 있다.

나는 find라는 함수를 이용해서 id_list.find(id_list.begin(), id_list.end(), "Muzi") - id_list.begin() 이렇게 해서 인덱스를 찾아냈다. 물론 이렇게 해도 통과를 받긴하지만, 다른 분들은 어떻게 했나 봤더니 map을 이용하신 분의 코드가 제일 효율적인 것 같았다..

map을 이용하면 더 빨리 ID인덱스를 찾을 수 있다. map은 키를 이용해서 값을 찾는 방식이므로 O(1)만에 인덱스를 찾을 수있다. 선언은 map Temp <string, int>;  이렇게 해주면된다. 만약 Muzi라는 유저의 ID 인덱스가 1이라고 하면Temp["Muzi"] == 1이다.

#include <string>
#include <vector>
#include <algorithm>
#include <string.h>
using namespace std;
const int MAX_N = 1000 + 5;
 
int get_idx(string str, vector<string> id_list);
vector<int> solution(vector<string> id_list, vector<string> report, int k) {
    vector<int> answer;
    sort(report.begin(), report.end());
    report.erase(unique(report.begin(), report.end()), report.end());
    vector<int> Who_reported[MAX_N];
    int count[MAX_N];
    memset(count, 0, sizeof(count));
    for (int i = 0; i < report.size(); i++) {
        int pos = report[i].find(" ", 0);
        string from = report[i].substr(0, pos);
        string to = report[i].substr(pos + 1, report[i].length());
        int from_idx = get_idx(from, id_list);
        int to_idx = get_idx(to, id_list);
        Who_reported[to_idx].push_back(from_idx);
        count[to_idx]++;
    }
    int copy_ans[MAX_N];
    memset(copy_ans, 0, sizeof(copy_ans));
    for (int i = 0; i < id_list.size(); i++) {
        if (count[i] >= k) {
            for (int j = 0; j < Who_reported[i].size(); j++) {
                copy_ans[Who_reported[i][j]]++;
            }
        }
    }
    for (int i = 0; i < id_list.size(); i++) {
        answer.push_back(copy_ans[i]);
    }
    return answer;
}
 
int get_idx(string str, vector<string> id_list){
    int ret = find(id_list.begin(), id_list.end(), str) - id_list.begin();
    return ret;
}

매번 백준만 풀다가, 코딩테스트 방식으로 연습하려고 오늘부터 코딩테스트 문제를 풀어보려한다.

1,2단계 문제는 대부분 문자열을 처리하는 문제가 많았다. 평소 풀던 백준문제는 문자열과 관련된 문제가 없어서 문자열을 처리하는게 아직 익숙하지 않다. 계속 문제를 풀어보면서 문자열 다루는 법을 익혀야겠다.