풀이

<aside> 💡 공부를 하면서도 추상화가 제대로 되지 않았다. 처음 문제를 풀 때도 이것을 어떻게 풀어야 하나 접근도 하기 힘든 문제였다. 두고두고 다시 풀어봐야겠다.

</aside>

// 1. 자료구조 세우기
unordered_map<string, unordered_set<string>> reports;
unordered_map<string, int> reported_count;

map은 Red-Black Tree를 이용한 자료구조이고, unordered_map은 Hash를 이용한 자료구조이다.

map은 <key, value> 쌍을 가지며, 입력과 동시에 정렬이 된다.(Red-Black Tree) 또한, 삽입/삭제/수정/탐색에 O(logN)의 시간이 걸린다.

unordered_map 도 <key, value> 쌍을 가지며, Hash Table을 이용한 자료구조이기 때문에 정렬이 되지 않는다. 하지만 해쉬테이블의 기본 원리상 보통 삽입, 삭제, 수정, 탐색에 O(1)이 걸린다. 하지만, 같은 hash index를 많이 가지는 경우 연결리스트랑 같기 때문에 최악의 경우 O(n)이다.

reports를 unordered_map<string, unordered_set<string>>으로 선언하였다. 이 자료구조는 A가 B를 신고했을 때, A(신고한 사람)를 기록하기 위함이다. 신고 당한사람은 중복될 수 없게 unordered_set<string>으로 선언하였다. 이때, set으로 선언해도 문제가 없지만, unordered_set이 set보다 평균적으로 더 빠른 삽입/검색를 지원하고, 정렬이 필요하지 않기 때문에 이렇게 선언한다.

reported_count는 unordered_map<string, int>로 선언했다. 이 자료구조는 신고당한 사람이 몇 번 신고당했는지를 기록하기 위한 자료구조이다.

// 2. report 정보 처리
for (auto r : report) {
	stringstream iss(r);
	string reporter, reported;
	iss >> reporter >> reported;
	
	if (reports[reporter].insert(reported).second) {
		reported_count[reported]++;
	}

stringstream의 기능을 처음 배웠다. 지금까지 백준을 풀 때는 입력을 내가 직접 입력하는 시스템이었다. 따라서 cin으로도 충분했다. cin은 공백을 기준으로 입력을 받는다. “apple banana cookie”라고 입력받을 때, cin >> a >> b >> c; 이렇게 입력받으면 cin은 공백을 기준으로 알아서 a = apple, b = banana 를 입력받는다. 하지만, 이번 문제처럼 이미 vector<string> report 로 주어지고, ["muzi frodo","apeach frodo","frodo neo","muzi neo","apeach muzi"] 이렇게 주어질 때는 어떻게 받는지 잘 몰랐다. report[0] = “muzi frodo” 인 식이다. 이를 위해 stringstream을 공부했다.

stringstream을 이용해서 문자열을 스트림으로 변환한다. report 정보 처리 부분은 알아둘 필요가 있을 것 같다.

reports의 신고 한 사람에 신고 당한 사람을 insert한다. 이때, 신고한 사람과 신고 당한 사람이 reports에 입력됬을때, reported_count[reported]++;한다. 즉 신고 당한 사람의 신고 횟수를 늘린다.

set과 unordered_set에서 insert 함수의 기능은 조금 다르다. 두 자료구조에서 insert 함수는 std::pair<iterator, bool>을 반환한다. 여기서 first는 삽입된 요소를 가리키는 반복자, second는 삽입 성공 여부를 나타내는 boolean이다.

즉, reports에 신고한 사람과 신고 당한 사람을 삽입하고 삽입이 성공했을 때, 신고 당한 사람의 신고 횟수를 증가시킨다. 이 모든 과정을 압축한 코드가 저 2줄인 셈이다.