[Programmers] Lv1)신고 주고 받기

Programmers Lv1) 신고 결과 받기

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

2022 Kakao Blind Recruitment에서의 기출 문제로, 프로그래머스의 레벨1에 해당하는 문제입니다. 또한 문제는 C++로 풀이되었습니다.

문제 풀이

• 문제에서의 해결해야 하는 핵심은 다음과 같습니다.

  1. ‘누가’ ‘누구에게’ 신고를 보내었는지가 하나의 문자열로 들어오기 때문에, 문자열을 잘라서 누가 누구에게 보내었는지 파악할 것.
  2. 한 사람이 동일 사람에게 신고를 보낼 경우 하나의 신고로만 처리할 것.
  3. 누가 누구에게 신고를 보내었는지 저장한 이후 누가 정지 대상인지 파악할 것.
  4. 파악한 정지 대상을 바탕으로 누가 메일을 받아야하는 사람인지 파악할 것.

1. ‘누가’ ‘누구에게’ 신고를 보내었는지 파악하기

• 누가 누구에게 신고를 보내었는지에 대한 정보가 문자열 vector로 주어집니다. 이때 report의 각 원소는 “이용자id 신고자id” 형태의 문자열입니다.
• 따라서 주어진 문자열을 공백(‘ ‘)을 기준으로 잘라서 저장할 필요가 있습니다.
• 필자의 경우 std::string의 find함수를 사용해서 공백의 위치를 찾고, 이후 공백을 기준으로 전과 후의 문자열을 각각 substr함수를 사용해서 분리한 후 따로 저장하였습니다.

    for (string temp : report) {
        int space_index = temp.find(' ');
        string from = temp.substr(0, space_index);
        string to = temp.substr(space_index+1, temp.size()-space_index);
          ...
    }

2. 한 사람이 동일 사람에게 신고를 보낼 경우 하나의 신고로만 처리할 것.

• 위 특성의 경우 set 또는 map을 이용하면 편리하게 풀어낼 수 있지만, 필자는 문구를 보고 set 또는 map을 활용할 생각을 미처 하지 못했습니다.
• 따라서 int 형태의 배열 또는 bool 형태의 배열을 생각해서, 신고를 보낸 경우 1 아니면 0으로 문제를 풀이하였습니다.

3. 누가 누구에게 신고를 보내었는지 저장한 후 누가 정지 대상인지 파악할 것.

• 누가 누구에게 신고를 보내었는지 알기 위해서 2차원 배열을 사용하였습니다.

• 2차원 배열을 사용하기 위해서 각각의 user들을 indexing 할 필요가 있었고, id_list의 몇 번째 원소인지를 활용해서 각각의 user들을 indexing 하였습니다.

• 따라서 이렇게 indexing하기 위해서 아래와 같은 함수를 만들어서 user_id의 string을 집어 넣으면 몇 번째 사람인지를 return 하는 또 다른 함수를 만들었습니다.

  int get_index (vector<string> id_list, string id) {
    for (int i=0;i<id_list.size();i++) {
        if (id_list[i] == id) return i;
    }
    return -1;
  }

• id_list의 길이는 2보다 크거나 같고 1000보다 같거나 작다고 명시되어 있습니다. 따라서 1000*1000 크기의 2차원 배열을 만들고, 각각의 칸을 ‘누가’ ‘누구에게’ 신고를 보내었다고 활용하였습니다.

  int from_to[1001][1001] = {}; //전역 변수

• 예를 들어서 0번 사용자가 5번 사용자에게 신고를 보내었다면, arr[0][5]의 값을 1로 바꾸어 주었습니다.

• 이렇게 해서 각 user가 누가 누구에게 신고를 받았는지 파악하고, 이를 통해서 누가 정지 대상인지도 추릴 수 있습니다.

4. 파악한 정지 대상을 바탕으로 누가 메일을 받아야 하는지 파악할 것.

• 누가 누구에게 신고를 보내었는지에 대한 정보는 전부 전역 변수로 선언하였던 2차원 배열에 모두 저장되어 있습니다.
• 따라서 정지 대상을 저장해 둔 vector 안의 원소들을 기준으로 탐색을 해서 만약 i번째 유저가 정지 대상을 신고했었다면, answer vector에 push 하는 int의 값을 1 더하는 식으로 진행합니다.

전체 코드

#include <string>
#include <vector>
#include <iostream>

using namespace std;

int from_to[1001][1001]={};

int get_index (vector<string> id_list, string id) {
    for (int i=0;i<id_list.size();i++) {
        if (id_list[i] == id) return i;
    }
    return -1;
}

vector<int> solution(vector<string> id_list, vector<string> report, int k) {
    vector<int> answer;
    int userNumber = id_list.size();

    for (string temp : report) {
        int space_index = temp.find(' ');
        string from = temp.substr(0, space_index);
        string to = temp.substr(space_index+1, temp.size()-space_index);

        int from_index = get_index(id_list, from);
        int to_index = get_index(id_list, to);

        if (from_to[from_index][to_index]==0) from_to[from_index][to_index]++;
    }

    vector<int> id_mail;
    for (int i=0; i<userNumber; i++) {
        int temp = 0;
        for (int j=0; j<userNumber; j++) {
            if (from_to[j][i]) temp++;
        }
        if (temp >= k) id_mail.push_back(i);
    }

    for (int i=0; i<userNumber;i++) {
        int each_answer = 0;
        for (int temp : id_mail) {
            if (from_to[i][temp]) each_answer++;
        }
        answer.push_back(each_answer);
    }
    return answer;
}

algorithm/신고 결과 받기.cpp at main · wkazxf/algorithm · GitHub