21. Uva-11286 Conformity

문제

<그림1: 문제설명>

문제는 N이 주어지고 N명의 학생이 듣는 5개의 수업이 주어진다. 이 때 한 명의 학생은 한 가지의 '수업 조합'을 갖게 된다. ex) 100 101 102 103 488을 듣는 학생은 {100,101,102,103,488}의 '수업 조합'을 갖게 된다. (문제에서 수업의 듣는 순서는 중요하지 않다.)

이 때 어떤 하나의 '수업 조합'이 몇 명의 학생에게서 나오는가를 popularity라 정의하자. 예를 들어 문제의 첫 sample input에서 {100,101,102,103,488}의 popularity는 2이다.

이 때 most popular, 즉 popularity가 가장 큰 수업을 듣는 학생의 수를 구하시오.

 

풀이) 나는 그냥 어떤 수업의 조합별로 그 수업이 나온 빈도를 체크한다음에 최대인 수업조합의 빈도수를 모두 더하는 방식을 택했다. 그 과정에서 C++ STL MAP(AVL GRAPH)을 이용했다. (key-Data구조가 필요하기 때문에)

이 때 map의 key는 수업조합이고 Data는 수업조합이 나온 횟수(frequency)이다. 코드는 다음과 같다.

 

#include<iostream>
#include <cstdio>
#include<algorithm>
#include<vector>
#include<map>
using namespace std;

int main() {
	int n,max_freq = 1,input,sum=0;
	int A[5];
	char buf[20];
	while (cin >> n&&n) {
		//initiallize
		map<string, int> freqmap;
		//input part
		for (int i = 0; i < n; i++) {
			string sequence;
			scanf("%d %d %d %d %d", &A[0], &A[1], &A[2], &A[3], &A[4]);
			sort(A, A + 5);
			sprintf(buf, "%d%d%d%d%d", A[0], A[1], A[2], A[3], A[4]);
			sequence = buf;
			freqmap[sequence]++;	
		}
		// find max_freq
		max_freq = 0;
		sum = 0;
		for (map<string, int>::iterator it = freqmap.begin(); it != freqmap.end(); it++) {
			if (it->second > max_freq) max_freq = it->second, sum=0;
			if (it->second == max_freq) sum += max_freq;
		}
		cout << sum << endl;
	}
	return 0;

}

 

위의 코드에서는 scanf로받고 sprinf로 string에 쑤셔넣었는데 사실 처음 코드에서는 for문 돌려가면서 string에 하나씩 push_back()을 했었다. 그런데 그렇게 하니까 logic은 동일한데도 WA판정이 계속 나왔다. 아마 그래서 sprinf가 뭔가 차이점이었던 것 같은데 그 부분을 다른 사람의 github에서 보고 따서 적용해봤더니 AC판정이 바로 났다. (무슨 차이인지 아직도 모르겠다) 앞으로는 애매해지면 input part는 ANSI C표준을 따라서 해보는 것도 괜찮을 것 같다.

(참고했던 github code: https://github.com/morris821028/UVa/blob/master/volume112/11286%20-%20Conformity%5BMap%5D.cpp)