ICPC 대비 문제 8. 호주식 투표법(Australian Voting)

>> 문제 8. 호주식 투표법(Australian Voting)

 

PC/UVa ID: 110108/10142, 인기도: B, 성공률: 낮음, 레벨: 1

 

>> 문제

호주식 투표 제도에서는 투표권자가 모든 후보에 대해 선호도 순으로 순위를 매긴다. 처음에는 1순위로 선택한 것만 집계하며 한 후보가 50% 초과 득표하면 그 후보가 바로 선출된다. 하지만 50% 초과 득표한 후보가 없으면 가장 적은 표를 받은 후보(둘 이상이 될 수도 있음)가 우선 탈락된다. 그리고 이렇게 탈락된 후보를 1순위로 찍었던 표만 다시 집계하여 아직 탈락되지 않은 후보들 가운데 가장 높은 선호도를 얻은 후보가 그 표를 얻는다. 이런 식으로 가장 약한 후보들을 탈락시키면서 그 다음 순위의 아직 탈락하지 않은 후보에게 표를 주는 과정을 50%가 넘는 표를 얻는 후보가 나오거나 탈락되지 않은 모든 후보가 동률이 될 때까지 반복한다.

 

>> 입력

입력 케이스의 개수를 나타내는 양의 정수 한 개가 들어있는 행으로 시작되며 그 줄에는 그 숫자밖에 입력되지 않는다. 그 뒤에는 빈 줄이 하나 들어가고 서로 다른 입력 케이스 사이에는 두 개의 빈 줄이 입력된다. 각 케이스의 첫번째 줄에는 후보 수를 나타내는 20이하의 정수 n이 입력된다. 그 밑으로 n개의 줄에 걸쳐서 후보의 이름이 순서대로 입력되며 각 후보의 이름을 80글자 이하로, 출력 가능한 문자로 구성된다. 그 뒤에는 최대 1,000줄이 입력될 수 있는데, 각 줄에는 투표 내역이 입력된다. 각 투표 내역에는 어떤 순서로 1 부터 n까지의 수가 입력된다. 첫번째 숫자는 1순위로 찍은 후보의 번호, 두번째 숫자는 2순위로 찍은 후보의 번호, 이런식으로 숫자가 기록된다.

 

>> 출력

각 테스트 게이스에 대해 당선된 후보의 이름 한줄, 또는 동률을 이룬 후보들의 이름이 들어있는 여러줄을 출력한다. 두 개 이상의 테스트 케이스가 있을 경우 각 결과는 한 개의 빈 줄로 구분한다.

 

>> 입력예 1   3 John Doe Jane Smith Sirhan Sirhan 1 2 3 2 1 3 2 3 1 1 2 3 3 1 2

>> 출력 예 John Doe

main.cpp

#include <iostream>
#include <string>
#include <sstream>
#include <vector>

using namespace std;

#define BALLOT		vector<int>
#define BALLOT_BOX	vector<BALLOT>

class Candidate{
	// 후보자 클래스.
public:
	Candidate(){}
	Candidate(const int & pIndex, const string & pName)
	{
		this->name = pName;
		this->index = pIndex;
		this->share = 0.0;
	}

	~Candidate(){
		// 투표함 폐기.
		BALLOT_BOX ::iterator it;

		for(it = this->ballotbox.begin(); it != this->ballotbox.end(); it++)
			(*it).erase((*it).begin(), (*it).end());

		this->ballotbox.erase(this->ballotbox.begin(), this->ballotbox.end());
	}

	string		name;
	int			index;
	// 투표즉시 후보자의 투표함에 넣어 계산을 쉽게하자.
	BALLOT_BOX	ballotbox;
	double		share;
};

#define CANDIDATES	vector<Candidate*>
class PollingPlace
{
public:
	PollingPlace(){}
	~PollingPlace(){}

private:
	typedef struct tag_progress{
		// 진행정보 구조체.
		typedef enum tagStatus{
			_BEGIN_ = 0,
			_BEFOR_CANDIDACY_,
			_CANDIDACY_,
			_VOTE_,
			_END_,
		}STATUS;
	private:
		STATUS status;
	public:
		int totalTestCase;	// 해야할 투표들
		int nowTestCase;	// 진행된 투표들
		int totalCandidates;// 입후보할 후보수
		int nowCandidates;	// 입후보한 후보수
		int voteCount;		// 투표수
		bool ballotCount;	// 개표 유무
	
		tag_progress() {
			nowCandidates = totalCandidates = 0;
			nowTestCase = totalTestCase =  0;
			voteCount = 0;
			ballotCount = false;
			status = tag_progress::_BEGIN_;
		}
	
		STATUS NowStatus(void) {
			// 리턴값에 따라 프로그램 진행이 달라짐.
			return status;
		}

		// 다음 진행상태로 변환한다.
		void NextStatus(void) {
			if ( status == _BEGIN_ && totalTestCase > 0)
				status = _BEFOR_CANDIDACY_;
			else if ( status == _BEFOR_CANDIDACY_ && totalCandidates > 0)
				status = _CANDIDACY_;
			else if ( status == _CANDIDACY_ && totalCandidates == nowCandidates)
				status = _VOTE_;
			else if ( status == _VOTE_ && ballotCount == true)
			{
				if ( ++nowTestCase < totalTestCase )
				{
					status = _BEFOR_CANDIDACY_;
					nowCandidates = totalCandidates = 0;
				}
				else
					status = _END_;

				ballotCount = false;
				voteCount = 0;
			}
			else if ( status == _VOTE_ && ballotCount == false)
				++voteCount;
		}
	}PROGRESS;
#define PRG tag_progress

	PROGRESS	progress;
	CANDIDATES	candidates;

public:
	bool CmdLine(const string& line)
	{
		bool ret = true;

		switch(progress.NowStatus())
		{
			case PRG::_BEGIN_:
				this->SetTestCase(line);	// 테스트 셋팅
				break;
			case PRG::_BEFOR_CANDIDACY_:
				this->SetCandidates(line);	// 입후보 셋팅
				break;
			case PRG::_CANDIDACY_:
				this->Candidacy(line);		// 입후보
				break;
			case PRG::_VOTE_:
				if ( line.length() > 0 &&		// 문자열이 있으면
					this->progress.voteCount <= 1000 )		
					this->Vote(line);		// - 투표
				else						// 없으면
					this->VoteCount();		// - 개표
				break;
			case PRG::_END_:
				ret = false;				// 종료
				break;
		}
		
		return ret;
	}

private:
	void SetTestCase(const string & cmd)
	{
		this->progress.totalTestCase = atoi(cmd.c_str());
		cout << endl;
		this->progress.NextStatus();
	}
	
	void SetCandidates(const string & cmd)
	{
		this->progress.totalCandidates = atoi(cmd.c_str());
		this->progress.NextStatus();
	}

	void Candidacy(const string & pName)
	{
		int len = pName.size();
		if (len > 0 && len <= 80)
		{
			this->candidates.push_back(new Candidate(this->candidates.size()+1, pName));
			++this->progress.nowCandidates;
			this->progress.NextStatus();
		}
	}

	void Vote(const string & cmd)
	{
		string buf;
		stringstream ss(cmd);

		vector<string> tokens;

		while ( ss >> buf )
			tokens.push_back(buf);

		// 투표가 제대로 된거라면.
		if ( tokens.size() == this->progress.totalCandidates )
		{
			// 무효표 검사.
			bool undervote = false;
			for(unsigned int i = 0; i < tokens.size(); i++)
			{
				int temp = atoi(tokens[i].c_str());
				if ( temp < 1 || temp > this->progress.totalCandidates)
					undervote = true;
			}

			if ( undervote == false)
			{
				BALLOT dummyBallot;
				// 투표용지를 만들고
				for(unsigned int i = 0; i < tokens.size(); i++)
					dummyBallot.push_back(atoi(tokens[i].c_str()));

				// 선호도가 1순위에 있는 사람 투표함에 바로 넣는다.
				int preference = atoi(tokens[0].c_str())-1;
				this->candidates[preference]->ballotbox.push_back(dummyBallot);
				
			}
		}
		
		// 무효표도 투표는 한거다.
		this->progress.NextStatus();
	}

	void VoteCount(void)
	{
		bool election = false;

		// 당선자를 찾을때까지 반복.
		while(election==false)
		{
			// 후보자들의 선호도를 계산한다.
			CANDIDATES ::iterator it;

			for(it = this->candidates.begin(); it != this->candidates.end(); it++)
				if ( this->progress.voteCount > 0 ) // 0을 나눌수 없다.
					(*it)->share = (double)(*it)->ballotbox.size()/(double)this->progress.voteCount*100.0;
			
			// 혹시 모를 모두다 동률이면
			double sami = (*this->candidates.begin())->share;
			bool samiflag = true;
			
			for(it = this->candidates.begin(); it != this->candidates.end(); it++)
				if ( (*it)->share != sami ) samiflag = false;

			if ( samiflag == true )
			{
				// 동률이면 그냥 이름 다 출력하고 나감.
				for(it = this->candidates.begin(); it != this->candidates.end(); it++)
					cout << (*it)->name << endl;
				cout << endl;

				election = true;
				break;
			}

			// 50% 이상인 후보자를 찾고.			
			for(it = this->candidates.begin(); it != this->candidates.end(); it++) {
				if( (*it)->share >= 50.0 )
				{
					election = true;
					break;
				}
			}
		
			// 50% 당선자가
			if ( election == true )
			{
				// 있으면 당선.
				cout << (*it)->name << endl << endl;				
			}
			else
			{	
				// 없으면, 최저율인 사람을 제거. 투표함을 넘김.
				this->TransBalllt();
				
			}
		}

		this->Release();
		this->progress.ballotCount = true;	// 개표끝.
		this->progress.NextStatus();
	}

	void TransBalllt(void)
	{
		// 최소값을 구할것이기 때문에 초기값은 최대값.
		double minShare = 100.0;	

		CANDIDATES ::iterator it;
		for(it = this->candidates.begin(); it != this->candidates.end(); it++)
			minShare = min(minShare, (*it)->share);

		for(it = this->candidates.begin(); it != this->candidates.end(); it++)
		{
			Candidate* Dummy = (*it);
			if ( minShare == Dummy->share )	// 최저율인 사람의
			{
				// 투표함을 뒤지면서 다음 후보자에게 분배한다.
				BALLOT_BOX ::iterator ballotit;
				
				for( ballotit = Dummy->ballotbox.begin(); ballotit != Dummy->ballotbox.end(); ballotit++)
				{
					// 자기 자신의 정보를 삭제하고.
					(*ballotit).erase((*ballotit).begin());
					
					// 투표용지를 다음 사람에게 넘긴다.
					this->candidates[((*ballotit)[0])-1]->ballotbox.push_back((*ballotit));
				}
				
				// 자신이 용지를 폐기처리.
				for( ballotit = Dummy->ballotbox.begin(); ballotit != Dummy->ballotbox.end(); ballotit++)
					(*ballotit).erase((*ballotit).begin(), (*ballotit).end());
				Dummy->ballotbox.erase(Dummy->ballotbox.begin(), Dummy->ballotbox.end());
			}
		}

	}

	void Release(void)
	{
		CANDIDATES ::iterator it;

		for(it = this->candidates.begin(); it != this->candidates.end(); it++)
		{
			Candidate* Dummy = (*it);
			BALLOT_BOX ::iterator ballotit;

			for( ballotit = Dummy->ballotbox.begin(); ballotit != Dummy->ballotbox.end(); ballotit++)
					(*ballotit).erase((*ballotit).begin(), (*ballotit).end());
			
			delete (*it);
			Dummy->ballotbox.erase(Dummy->ballotbox.begin(), Dummy->ballotbox.end());
		}
		this->candidates.erase(this->candidates.begin(), this->candidates.end());
	}

};

void main(void)
{
	PollingPlace pp;
	bool Keep = true;

	while(Keep)
	{
		string cmd;
		::getline(cin, cmd);
		Keep = pp.CmdLine(cmd);
	}
}

try catch는 머나먼 곳으로...

언제나 메모리 해제 하는 부분에서 문제가 생기는거 같다.