🔵 문제 링크
https://school.programmers.co.kr/learn/courses/30/lessons/92334
프로그래머스
SW개발자를 위한 평가, 교육의 Total Solution을 제공하는 개발자 성장을 위한 베이스캠프
programmers.co.kr
🔵 문제 접근
문제를 정리해 보면 다음과 같다.
- 유저는 여러 명을 신고할 수 있다.
- 한 유저가 같은 유저를 여러번 신고한다면 그건 1번으로 처리한다.
- 신고 횟수가 k 이상 누적되면 그 사람을 신고한 사람에게 정지 메일이 발송됨.
여기서 (신고당한 유저 - 신고한 사람) map 구조를 사용해야 한다는 걸 떠올렸다.
신고 당한 횟수가 얼마나 누적되었는지가 답에 영향을 미치기 때문에, 신고당한 유저를 key값으로 설정했다.
value는 한 유저가 같은 유저를 여러번 신고할 수 없기 때문에, 중복 신고 방지가 가능한 set을 선택하였다.
답은 map을 돌면서 value.size()가 k 이상임을 확인하여 정지 메일 발송을 처리하면 된다.
🔵 전체 코드
#include <string>
#include <vector>
#include <sstream>
#include <unordered_set>
#include <unordered_map>
using namespace std;
// 유저 신고 -> (여러 명 신고 가능)
// 한 유저가 같은 유저를 계속 신고하면 그건 1번 처리
// 신고 횟수가 k가 되면 유저 당 정지 메일 발송
// 신고 당한 사람 - 신고한 사람 set(중복 신고 방지)?
// set size가 k를 넘기면 id_list에 담긴 id(신고한 사람) 순서대로 결과 메일 수 담기
vector<int> solution(vector<string> id_list, vector<string> report, int k)
{
vector<int> answer(id_list.size());
unordered_map<string, int> userTable;
unordered_map<string, unordered_set<string>> reportTable;
// 이름으로 id 값을 바로 찾기 위해 hash 생성
for (int i = 0; i < id_list.size(); i++)
userTable[id_list[i]] = i;
// 각 id 별로 신고당한 횟수와 신고한 사람(set으로 중복 x) 누적
for (int i = 0; i < report.size(); i++)
{
// 공백으로 신고한 사람, 신고당한 사람 구분
stringstream ss(report[i]);
string reporter = "";
string reportee = "";
ss >> reporter >> reportee;
reportTable[reportee].insert(reporter);
}
// 신고 횟수가 k 이상인 사람 구별 후 신고자에게 메일 전송
for (const auto& pair : reportTable)
{
if (pair.second.size() >= k)
{
for (string name : pair.second)
{
int userId = userTable[name];
answer[userId]++;
}
}
}
return answer;
}
🔵 시간 복잡도
첫 번째 for문에서 id_list는 최대 1000이므로 상수로 취급할 수 있다.
두 번째 for문에서 report의 최대 길이를 N이라 했을 때, 시간 복잡도는 O(N)이다. (unordered_set의 insert 연산은 평균적으로 O(1)이다.)
세 번째 for문이 중요한데, 이중 for문이지만 시간 복잡도는 O(N)이다.
reportTable을 순회하며 각 set의 길이만큼 순회하는 것이지만, 이는 결국 중복 신고를 제외한 report 배열의 길이와 같다.
즉, 최악의 경우(중복이 없을 경우) O(N = report 길이)인 것이다.
따라서 이 코드의 시간 복잡도는 O(N)이다.
'PS' 카테고리의 다른 글
| [C++] Programmers Lv. 2 "예상 대진표" (0) | 2025.05.30 |
|---|---|
| [C++] Programmers Lv. 2 "메뉴 리뉴얼" (0) | 2025.05.30 |
| [C++] Programmers Lv. 3 "베스트앨범" (0) | 2025.05.27 |
| [C++] Programmers Lv. 2 "오픈 채팅방" (0) | 2025.05.27 |
| [C++] Programmers Lv. 2 "할인 행사" (0) | 2025.05.24 |