AustralianVoting/곽세환

소감

2005/03/13 Accepted(P.E.) 0:01.191 520 처음 접근방법이 잘못돼 하루종일 고생했다. 복잡한 코드는 감당할수 없는 버그가 생긴다 문제를 제대로 이해해야한다. 코딩하기전 생각하는 시간을 많이 가지자 다른 문제들 같았으면 투표자수를 입력받았을텐데 이 문제는 그렇지 않다. 그래서 쫌 성가신 측면이 있다. 문제를 풀었을때의 기분은 수많은 삽질의 스트레스를 한번에 날려준다.

소스

#include <iostream>
using namespace std;
#include <stdlib.h>
#include <string.h>

int main()
{
	int numberOfCase;
	cin >> numberOfCase;
	int i, tc;
	for (tc = 0; tc < numberOfCase; tc++)
	{
		int numberOfCandidates;
		char candidates[20][81];
		int votes[1000][20] = Template:0;
		int rank[1000] = Template:0;
		int votesPerCandidates[20] = Template:0;
		
		cin >> numberOfCandidates;
		cin.get();
		for (i = 0; i < numberOfCandidates; i++)
			cin.getline(candidates[i], 81);

		int numberOfVoters = 0;
		char temp[60];

		
		while (cin.getline(temp, 60) && strcmp(temp, ""))
		{
			votes[numberOfVoters][0] = atoi(strtok(temp, " "));
			for (i = 1; i < numberOfCandidates; i++)
				votes[numberOfVoters][i] = atoi(strtok(NULL, " "));
			numberOfVoters++;
		}

		bool foundWinner = false;
		bool foundTie = true;
		int winner;
		int sameVote;
		
		int eliminated[20];
		int eliminatedCnt = 0;
		while (true)
		{
			for (i = 0; i < numberOfCandidates; i++)
			{
				votesPerCandidates[i] = 0;
			}

			// 후보자 개인당 득표수를 구한다
			for (i = 0; i < numberOfVoters; i++)
			{
				votesPerCandidates[votes[i][rank[i]] - 1]++;
			}

			// 테스트 출력(후보자 개인당 득표수)
			/*for (i = 0; i < numberOfCandidates; i++)			
				cout << votesPerCandidates[i] << " ";
			cout << endl;*/
			
			// 테스트 출력(누가 누구 선택했는지)
			/*for (i = 0; i < numberOfVoters; i++)
			{
				cout << votes[i][rank[i]] << " ";
			}
			cin.get();*/

			// 한명이 50% 초과거나 득표수가 모두 같으면 종료
			for (i = 0; i < numberOfCandidates; i++)
			{
				if (votesPerCandidates[i] > 0.5 * numberOfVoters)
				{
					foundWinner = true;
					winner = i;
					break;
				}
			}
			foundTie = true;
			sameVote = 0;
			for (i = 0; i < numberOfCandidates; i++)
			{
				if (votesPerCandidates[i] == 0)
					continue;
				if (sameVote == 0)
					sameVote = votesPerCandidates[i];
				else if (sameVote != votesPerCandidates[i])
					foundTie = false;
			}
			if (foundWinner || foundTie)
				break;

			// 가장 적은 득표수를 받은 후보자를 찍은 유권자들은 후보자 선택을 그 후순위자로 선택(2단계)
			int minVote = 1001;
			for (i = 0; i < numberOfCandidates; i++)
			{
				if (votesPerCandidates[i] == 0)
					continue;
				if (minVote > votesPerCandidates[i])
					minVote = votesPerCandidates[i];
			}

			// 1-제거될 후보자 목록 만들고
			for (i = 0; i < numberOfVoters; i++)
			{
				int j;
				if (votesPerCandidates[votes[i][rank[i]] - 1] == minVote)
				{
					for (j = 0; j < eliminatedCnt; j++)
					{
						if (eliminated[j] == votes[i][rank[i]])
							break;
					}
					if (j == eliminatedCnt)
						eliminated[eliminatedCnt++] = votes[i][rank[i]];
				}
			}

			// 2-제거될 후보자 목록에 없는 사람중에서 선택
			for (i = 0; i < numberOfVoters; i++)
			{
				int j;
				if (votesPerCandidates[votes[i][rank[i]] - 1] == minVote)
				{
					bool foundNextCandidates;
					while (true)
					{
						rank[i]++;
						
						foundNextCandidates = true;
						for (j = 0; j < eliminatedCnt; j++)
							if (votes[i][rank[i]] == eliminated[j])
							{
								foundNextCandidates = false;
								break;
							}
						if (foundNextCandidates)
							break;
					}
				}
			}
			// 테스트 출력(제거된 명단)
			/*for (i = 0; i < eliminatedCnt; i++)
				cout << eliminated[i] << " ";
			cout << endl;*/
		}
		if (foundWinner)
			cout << candidates[winner] << endl;
		else if (foundTie)
		{
			for (i = 0; i < numberOfCandidates; i++)
			{
				if (sameVote == votesPerCandidates[i])
					cout << candidates[i] << endl;
			}
		}
		cout << endl;
	}

	return 0;
}

댓글

---

AustralianVoting