[백준 25325] 학생 인기도 측정 (C++)

https://www.acmicpc.net/problem/25325

문제

---

학생 이름이 공백으로 구분된 문자열 A가 주어진다. 문자열 A에는 중복된 학생 이름이 존재하지 않는다. 학생 이름은 알파벳 소문자로 이루어져 있다. 각 학생이 좋아하는 학생의 학생 이름 목록이 공백으로 구분된 문자열로 주어진다. 각 학생이 좋아하는 학생은 1명 이상 주어지고, 내가 나를 좋아하는 예는 없다. 나를 좋아하는 학생이 많을수록 나의 인기도가 높다. 인기도가 높은 학생부터 낮은 학생 순으로 학생 이름과 해당 학생을 좋아하는 학생 수를 출력하자. 인기도가 같은 경우 학생 이름 기준으로 오름차순으로 출력하자.

 

입력

---

첫 번째 줄에 학생 수 n이 주어진다.

두 번째 줄에 n명의 학생 이름이 공백으로 구분된 문자열 A가 주어진다.

다음 줄부터 n개의 줄에 걸쳐 한 줄에 한 학생의 정보가 주어진다. 학생 정보는 문자열 A에 나온 학생 순서대로 주어진다. 한 명의 학생 정보는 해당 학생이 좋아하는 학생 이름이 공백으로 구분된 문자열로 주어진다.

 

출력

---

첫 번째 줄부터 n번째 줄까지 학생 이름과 해당 학생을 좋아하는 학생 수를 공백으로 구분하여 한 줄에 출력한다. 인기도가 높은 학생부터 낮은 학생 순으로 출력하고, 인기도가 같은 경우 학생 이름 기준으로 오름차순으로 출력한다.

 

제한

---

• 3 ≤ n ≤ 100
• 1 ≤ 학생 이름 길이 ≤ 10

 

문제 풀이

---

정렬 문제.

 

각 학생별로 좋아하는 학생 수를 배열로 만들어 기록해주면 된다. 학생 이름으로만 배열에서 몇번째인지 찾을 수 없으므로 이름을 키로 하고 해당 학생의 인덱스를 값으로 하는 map을 하나 생성하여 해당 map에 정보를 저장한다.

c++에서 cin으로는 공백이 있는 문자열을 받을 수 없으므로, getline()을 이용해 좋아하는 학생이 여러 명 있는 문자열을 입력받고, stringstream으로 공백을 기준으로 문자열을 나누어준다. 잘려서 생성된 토큰이 좋아하는 학생 중 한 명이므로, map에서 인덱스를 찾아 인기도를 올려준다.

모든 입력을 다 받았다면 인기도가 높은 순, 인기도가 같다면 이름 순으로 정렬한다. pair<int, string>으로 배열을 만들어 인기도를 부호를 바꾸어 저장하면 정렬 하는 방법의 재정의가 필요 없이 기본 sort()로 답을 구할 수 있다.

 

아래는 코드.

#include <iostream>
#include <utility>
#include <sstream>
#include <map>
#include <algorithm>
using namespace std;

int main()
{
	cin.tie(NULL);
	ios::sync_with_stdio(false);

	int N;
	string str, token;
	cin >> N;
	pair<int, string>* students = new pair<int, string>[N];
	map<string, int> index;
	map<string, int>::iterator it;
	for (int i = 0; i < N; i++)
	{
		cin >> students[i].second;
		students[i].first = 0;
		index.insert({ students[i].second, i });
	}
	cin.ignore();
	for (int i = 0; i < N; i++)
	{
		getline(cin, str);
		stringstream ss(str);
		while (ss >> token)
		{
			it = index.find(token);
			students[it->second].first--;
		}
	}
	sort(students, students + N);
	for (int i = 0; i < N; i++)
	{
		cout << students[i].second <<" "  <<- students[i].first << "\n";
	}
	return 0;
}