Talsu.net :: Programming Challenges - 호주식 투표법(Australian Voting)

Study/Programming Challenges2009/10/08 22:55

Programming Challenges - 호주식 투표법(Australian Voting)

문제 <- 클릭

아.. 이건 또 뭐가 문제지...? 체스 문제 처럼 나중에 다시보면 또 눈에 보이겠지.
시간 낭비는 하지말자.. 바쁘다!

#include <iostream>
#include <sstream>
#include <vector>
#include <string>
typedef std::vector<int> Numbers;
class AustralianVoting {
	std::vector<std::string> candidates;
	std::vector<Numbers> persons;
	std::vector<int> votes;
	std::vector<int> eliminated;

bool checkMoreVotes() {
		int max = 0;
		std::vector<int>::iterator it;
		for (it = votes.begin(); it != votes.end(); ++it) {
			if (max < *it)
				max = *it;
			//			std::cout << *it << std::endl;
		}

if (max > (int) persons.size() / 2) {
			//			std::cout << "max > 50% : No more...." << std::endl;
			return false;
		} else if (votesAreSame()) {
			//			std::cout << "Alive are Same : No more...." << std::endl;
			return false;
		}
		//		std::cout << "More.." << std::endl;
		return true;
	}

bool votesAreSame() {
		bool flag = true;
		int pre;
		int index = 0;
		std::vector<int>::iterator it;
		for (it = votes.begin(); it != votes.end(); ++it) {
			if (!eliminatedHas(index)) {
				if (flag) {
					pre = *it;
					flag = false;
				} else {
					if (pre != *it)
						return false;
				}
			}
			++index;
		}

return true;
	}

int getBest() {
		int max = 0;
		int index = 0;
		std::vector<int>::iterator it;
		for (it = votes.begin(); it != votes.end(); ++it) {
			if (!eliminatedHas(index)) {
				if (max < *it)
					max = *it;
			}
			++index;
		}

return max;
	}

int getWorst() {
		bool flag = true;
		int min = 1000;
		int index = 0;
		std::vector<int>::iterator it;
		for (it = votes.begin(); it != votes.end(); ++it) {
			if (!eliminatedHas(index)) {
				if (flag) {
					min = *it;
					flag = false;
				} else {
					if (min > *it)
						min = *it;
				}
			}
			++index;
		}
		return min;
	}

bool eliminatedHas(int val) {
		std::vector<int>::iterator it;
		for (it = eliminated.begin(); it != eliminated.end(); ++it) {
			if (*it == val)
				return true;
		}
		return false;
	}

void voteR(std::vector<Numbers>& vec, int depth) {
		if (depth > (int) candidates.size() - 1)
			return;
		//		std::cout << "depth = " << depth << std::endl;
		int sizeI = vec.size();
		int sizeJ = votes.size();

for (int i = 0; i < sizeI; ++i) {
			if (!eliminatedHas(vec[i][depth]))
				votes[vec[i][depth]] = votes[vec[i][depth]] + 1;
		}
		int worst = getWorst();

if (checkMoreVotes()) {
			std::vector<Numbers> store;

for (int j = 0; j < sizeJ; ++j) {
				if (!eliminatedHas(j)) {
					if (votes[j] == worst) {
						eliminated.push_back(j);
						//						std::cout << j << " : eliminated(" <<votes[j]<<")("<<worst<<")"<< std::endl;
						for (int i = 0; i < sizeI; ++i) {
							if (vec[i][depth] == j) {
								store.push_back(vec[i]);
							}
						}
					}
				}
			}

voteR(store, ++depth);
		} else {
			return;
		}

}

public:

void vote() {

voteR(persons, 0);

int index = 0;
		std::vector<int>::iterator it;
		for (it = votes.begin(); it != votes.end(); ++it) {
			if (!eliminatedHas(index)) {
				if (*it == getBest())
					std::cout << candidates[index] << std::endl;
			}
			++index;
		}
	}

void reset() {
		candidates.clear();
		persons.clear();
		votes.clear();
		eliminated.clear();
	}

void printNumbers() {
		int sizeI = persons.size();
		int sizeJ = candidates.size();

for (int i = 0; i < sizeI; ++i) {
			for (int j = 0; j < sizeJ; ++j) {
				std::cout << persons[i][j] << " ";
			}
			std::cout << std::endl;
		}
	}

void pushNumbers(Numbers& numbers) {
		persons.push_back(numbers);
	}

void pushCandidates(std::string& name) {
		candidates.push_back(name);
		votes.push_back(0);
	}

};

int main() {
	AustralianVoting av;
	std::string buffer;
	int numberOfCase;
	int numberOfCandidates;
	std::cin >> numberOfCase;
	std::getline(std::cin, buffer);
	for (int i = 0; i < numberOfCase; ++i) {
		if (i != 0)
			std::cout << std::endl;
		std::cin >> numberOfCandidates;
		//		std::cout<<"numberOf Candidates : "<<numberOfCandidates<<std::endl;
		std::getline(std::cin, buffer);
		for (int j = 0; j < numberOfCandidates; ++j) {
			std::getline(std::cin, buffer);
			av.pushCandidates(buffer);
		}
		//		std::cout<<"pushNames Done.."<<std::endl;

int emptyCounter = 0;
		while (emptyCounter < 2) {
			std::getline(std::cin, buffer);
			if (buffer.empty()) {
				emptyCounter++;
			} else {
				Numbers nums;
				std::istringstream iss(buffer);

int num;
				while (iss >> num) {
					nums.push_back(num - 1);
				}
				//				std::cout<<"nums size : "<<nums.size()<<std::endl;

av.pushNumbers(nums);

}
		}

//				av.printNumbers();
		av.vote();
		av.reset();

}

return 0;
}

크리에이티브 커먼즈 라이선스

이 저작물은 크리에이티브 커먼즈 코리아 저작자표시-비영리-동일조건변경허락 2.0 대한민국 라이선스에 따라 이용하실 수 있습니다.

'Study > Programming Challenges' 카테고리의 다른 글

Programming Challenges - 포커 패 (Poker Hands) (0)	2009/10/12
Programming Challenges - 유쾌한 점퍼(Jolly Jumpers) (0)	2009/10/11
Programming Challenges - 호주식 투표법(Australian Voting) (0)	2009/10/08
Programming Challenges - 체크 확인 (Check the Check) (1)	2009/10/05
Programming Challenges - 인터프리터(Interpreter) (2)	2009/10/04
Programming Challenges - 그래픽 편집기 (Graphical Editor) (2)	2009/10/02

Posted by 탈수

TAG Algorithm, Australian Voting, Programming Challenges, voting, 알고리즘, 투표, 호주식 투표법

Trackback 0 Comment 0

«이전 1 ... 8 9 10 11 12 13 14 15 16 ... 98 다음»

일	월	화	수	목	금	토
				1	2	3
4	5	6	7	8	9	10
11	12	13	14	15	16	17
18	19	20	21	22	23	24
25	26	27	28	29	30	31

태터데스크 관리자

태터데스크 메시지

Talsu.net

Programming Challenges - 호주식 투표법(Australian Voting)

'Study > Programming Challenges' 카테고리의 다른 글

TRACKBACK http://talsu.net/trackback/122

카테고리

공지사항

태그목록

최근에 올라온 글

최근에 달린 댓글

최근에 받은 트랙백

글 보관함

달력

링크