[BOJ] C++ 2456번 나는 학급회장이다

 

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

2456번: 나는 학급회장이다

 

각각의 후보에 대한 구조체를 만들어 정보를 관리한다.

struct candidate {
	int num = 0;		//몇번 째 후보인가
	int score[4] = {};	//score[0] :누적 점수 ,
    				//index 1~3 : 각각 1,2,3점을 받은 횟수
	bool same = 0;		//회장을 결정할 수 없는 경우인지 체크
};

 

 

조건에 맞춰 후보들을 아래 조건에 맞춰 정렬해준다.

 

[조건]

1. 가장 큰 점수를 받은 후보가 회장

2. 점수가 동일하다면 3점 득표가 많은 후보가 회장

3. 1,2번이 동일하다면 2점 득표가 많은 후보가 회장

4. 1,2,3번이 동일하다면 1점 득표가 많은 후보가 회장

5. 1,2,3,4가 모두 동일하다면 회장을 결정하지 못함

 

5번의 경우, 두 후보가 동일한 득표를 했음을 체크하기 위하여 두 후보의 same 변수를 1로 만들어 유일하지 않음을 체크해준다.

bool cmp(candidate& x, candidate& y) {
	if (x.score[0] == y.score[0]) {
		if (x.score[3] == y.score[3]) {
			if (x.score[2] == y.score[2]) {
				if (x.score[1] == y.score[1]) {	//회장을 결정할 수 없음
					x.same = 1;
					y.same = 1;
					return x.score[1] < y.score[1];
				}
				else return x.score[1] < y.score[1];
			}
			else return x.score[2] < y.score[2];
		}
		else return x.score[3] < y.score[3];
	}
	else return x.score[0] < y.score[0];

}

 

 

main 함수에서 1,2,3번 후보를 선언해준 뒤 투표자 n의 수를 입력 받는다.

이때, 후보 구조체 선언은 비교와 정렬을 쉽게 하기 위하여 벡터로 만들어 관리해준다.

vector<candidate> c;
for (int i = 0; i < 3; i++) {
	candidate cc;
	cc.num = i + 1;
	c.push_back(cc);
}
    
int n = 0;
cin >> n;

 

 

while문을 통해 각각의 투표자로부터 후보자 점수를 입력 받는다.

이때 후보자 구조체에서 score[0]에 누적점수를, score[1~3] 중 하나에 어떤 점수를 득표했는지 횟수를 카운트한다.

 

만약 2점을 득표했다면

score[0] += 2; // 누적점수

score[2]++; //2점 득표 카운트

가 된다.

while (n--) {
		int vote[3];
		cin >> vote[0] >> vote[1] >> vote[2];

		//후보자 1
		c[0].score[0] += vote[0];
		c[0].score[vote[0]]++;
		//후보자 2
		c[1].score[0] += vote[1];
		c[1].score[vote[1]]++;
		//후보자 3
		c[2].score[0] += vote[2];
		c[2].score[vote[2]]++;
	}

 

 

sort함수를 통해 위에서 정의해준 cmp 조건에 맞춰 정렬해준다.

최종 회장 후보가 벡터의 가장 뒤에 오도록 정렬된다.

sort(c.begin(), c.end(), cmp);

 

 

최종 회장후보가 유일하다면 후보의 num과 최종 누적 점수를 출력하고,

유일하지 않다면 0과 가장 큰 점수를 얻은 후보의 최종 누적 점수를 출력한다.

if (c[2].same != 1) {
	cout << c[2].num << " " << c[2].score[0];
}
else {
	cout << 0 <<" "<< c[2].score[0];
}

 

위의 내용을 하나로 정리하면 아래와 같다.

---

[BOJ-2456.cpp]

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

struct candidate {
	int num = 0;
	int score[4] = {};	//score[0] :누적 점수 ,
				//index 1~3 : 각각 1,2,3점을 받은 횟수
	bool same = 0;
};

bool cmp(candidate& x, candidate& y) {
	if (x.score[0] == y.score[0]) {
		if (x.score[3] == y.score[3]) {
			if (x.score[2] == y.score[2]) {
				if (x.score[1] == y.score[1]) {
					x.same = 1;
					y.same = 1;
					return x.score[1] < y.score[1];
				}
				else return x.score[1] < y.score[1];
			}
			else return x.score[2] < y.score[2];
		}
		else return x.score[3] < y.score[3];
	}
	else return x.score[0] < y.score[0];

}

int main() {

	int n = 0;
	cin >> n;

	vector<candidate> c;
	for (int i = 0; i < 3; i++) {
		candidate cc;
		cc.num = i + 1;
		c.push_back(cc);
	}

	while (n--) {
		int vote[3];
		cin >> vote[0] >> vote[1] >> vote[2];

		//후보자 1
		c[0].score[0] += vote[0];
		c[0].score[vote[0]]++;
		//후보자 2
		c[1].score[0] += vote[1];
		c[1].score[vote[1]]++;
		//후보자 3
		c[2].score[0] += vote[2];
		c[2].score[vote[2]]++;
	}

	
	sort(c.begin(), c.end(), cmp);

	if (c[2].same != 1) {
		cout << c[2].num << " " << c[2].score[0];
	}
	else {
		cout << 0 <<" "<< c[2].score[0];
	}
}