{"id":2239,"date":"2009-10-08T13:55:02","date_gmt":"2009-10-08T13:55:02","guid":{"rendered":"http:\/\/192.168.0.71:9090\/?p=1941"},"modified":"2009-10-08T13:55:02","modified_gmt":"2009-10-08T13:55:02","slug":"programming-challenges-%ed%98%b8%ec%a3%bc%ec%8b%9d-%ed%88%ac%ed%91%9c%eb%b2%95australian-voting","status":"publish","type":"post","link":"https:\/\/talsu.net\/?p=2239","title":{"rendered":"Programming Challenges &#8211; \ud638\uc8fc\uc2dd \ud22c\ud45c\ubc95(Australian Voting)"},"content":{"rendered":"<p><span style=\"font-size: 12pt; font-weight: bold;\"><a title=\"[http:\/\/programming-challenges.com\/pg.php?page=downloadproblem&amp;probid=110108&amp;format=html]\ub85c \uc774\ub3d9\ud569\ub2c8\ub2e4.\" target=\"_blank\" href=\"http:\/\/programming-challenges.com\/pg.php?page=downloadproblem&amp;probid=110108&amp;format=html\">\ubb38\uc81c &lt;- \ud074\ub9ad<\/a><\/span><\/p>\n<p>\uc544.. \uc774\uac74 \ub610 \ubb50\uac00 \ubb38\uc81c\uc9c0&#8230;? \uccb4\uc2a4 \ubb38\uc81c \ucc98\ub7fc \ub098\uc911\uc5d0 \ub2e4\uc2dc\ubcf4\uba74 \ub610 \ub208\uc5d0 \ubcf4\uc774\uaca0\uc9c0.<br \/>\n\uc2dc\uac04 \ub0ad\ube44\ub294 \ud558\uc9c0\ub9d0\uc790.. \ubc14\uc058\ub2e4!<\/p>\n<pre class=\"lang:c++ decode:true\">#include <iostream>\n#include <sstream>\n#include <vector>\n#include <string>\ntypedef std::vector<int> Numbers;\nclass AustralianVoting {\n\tstd::vector<std::string> candidates;\n\tstd::vector<numbers> persons;\n\tstd::vector<int> votes;\n\tstd::vector<int> eliminated;\n\n\tbool checkMoreVotes() {\n\t\tint max = 0;\n\t\tstd::vector<int>::iterator it;\n\t\tfor (it = votes.begin(); it != votes.end(); ++it) {\n\t\t\tif (max < *it)\n\t\t\t\tmax = *it;\n\t\t\t\/\/\t\t\tstd::cout << *it << std::endl;\n\t\t}\n\n\t\tif (max > (int) persons.size() \/ 2) {\n\t\t\t\/\/\t\t\tstd::cout << \"max > 50% : No more....\" << std::endl;\n\t\t\treturn false;\n\t\t} else if (votesAreSame()) {\n\t\t\t\/\/\t\t\tstd::cout << \"Alive are Same : No more....\" << std::endl;\n\t\t\treturn false;\n\t\t}\n\t\t\/\/\t\tstd::cout << \"More..\" << std::endl;\n\t\treturn true;\n\t}\n\n\tbool votesAreSame() {\n\t\tbool flag = true;\n\t\tint pre;\n\t\tint index = 0;\n\t\tstd::vector<int>::iterator it;\n\t\tfor (it = votes.begin(); it != votes.end(); ++it) {\n\t\t\tif (!eliminatedHas(index)) {\n\t\t\t\tif (flag) {\n\t\t\t\t\tpre = *it;\n\t\t\t\t\tflag = false;\n\t\t\t\t} else {\n\t\t\t\t\tif (pre != *it)\n\t\t\t\t\t\treturn false;\n\t\t\t\t}\n\t\t\t}\n\t\t\t++index;\n\t\t}\n\n\t\treturn true;\n\t}\n\n\tint getBest() {\n\t\tint max = 0;\n\t\tint index = 0;\n\t\tstd::vector<int>::iterator it;\n\t\tfor (it = votes.begin(); it != votes.end(); ++it) {\n\t\t\tif (!eliminatedHas(index)) {\n\t\t\t\tif (max < *it)\n\t\t\t\t\tmax = *it;\n\t\t\t}\n\t\t\t++index;\n\t\t}\n\n\t\treturn max;\n\t}\n\n\tint getWorst() {\n\t\tbool flag = true;\n\t\tint min = 1000;\n\t\tint index = 0;\n\t\tstd::vector<int>::iterator it;\n\t\tfor (it = votes.begin(); it != votes.end(); ++it) {\n\t\t\tif (!eliminatedHas(index)) {\n\t\t\t\tif (flag) {\n\t\t\t\t\tmin = *it;\n\t\t\t\t\tflag = false;\n\t\t\t\t} else {\n\t\t\t\t\tif (min > *it)\n\t\t\t\t\t\tmin = *it;\n\t\t\t\t}\n\t\t\t}\n\t\t\t++index;\n\t\t}\n\t\treturn min;\n\t}\n\n\tbool eliminatedHas(int val) {\n\t\tstd::vector<int>::iterator it;\n\t\tfor (it = eliminated.begin(); it != eliminated.end(); ++it) {\n\t\t\tif (*it == val)\n\t\t\t\treturn true;\n\t\t}\n\t\treturn false;\n\t}\n\n\tvoid voteR(std::vector<numbers>& vec, int depth) {\n\t\tif (depth > (int) candidates.size() - 1)\n\t\t\treturn;\n\t\t\/\/\t\tstd::cout << \"depth = \" << depth << std::endl;\n\t\tint sizeI = vec.size();\n\t\tint sizeJ = votes.size();\n\n\t\tfor (int i = 0; i < sizeI; ++i) {\n\t\t\tif (!eliminatedHas(vec[i][depth]))\n\t\t\t\tvotes[vec[i][depth]] = votes[vec[i][depth]] + 1;\n\t\t}\n\t\tint worst = getWorst();\n\n\t\tif (checkMoreVotes()) {\n\t\t\tstd::vector<numbers> store;\n\n\t\t\tfor (int j = 0; j < sizeJ; ++j) {\n\t\t\t\tif (!eliminatedHas(j)) {\n\t\t\t\t\tif (votes[j] == worst) {\n\t\t\t\t\t\teliminated.push_back(j);\n\t\t\t\t\t\t\/\/\t\t\t\t\t\tstd::cout << j << \" : eliminated(\" <<votes[j]<<\")(\"<<worst<<\")\"<< std::endl;\n\t\t\t\t\t\tfor (int i = 0; i < sizeI; ++i) {\n\t\t\t\t\t\t\tif (vec[i][depth] == j) {\n\t\t\t\t\t\t\t\tstore.push_back(vec[i]);\n\t\t\t\t\t\t\t}\n\t\t\t\t\t\t}\n\t\t\t\t\t}\n\t\t\t\t}\n\t\t\t}\n\n\t\t\tvoteR(store, ++depth);\n\t\t} else {\n\t\t\treturn;\n\t\t}\n\n\t}\n\npublic:\n\n\tvoid vote() {\n\n\t\tvoteR(persons, 0);\n\n\t\tint index = 0;\n\t\tstd::vector<int>::iterator it;\n\t\tfor (it = votes.begin(); it != votes.end(); ++it) {\n\t\t\tif (!eliminatedHas(index)) {\n\t\t\t\tif (*it == getBest())\n\t\t\t\t\tstd::cout << candidates[index] << std::endl;\n\t\t\t}\n\t\t\t++index;\n\t\t}\n\t}\n\n\tvoid reset() {\n\t\tcandidates.clear();\n\t\tpersons.clear();\n\t\tvotes.clear();\n\t\teliminated.clear();\n\t}\n\n\tvoid printNumbers() {\n\t\tint sizeI = persons.size();\n\t\tint sizeJ = candidates.size();\n\n\t\tfor (int i = 0; i < sizeI; ++i) {\n\t\t\tfor (int j = 0; j < sizeJ; ++j) {\n\t\t\t\tstd::cout << persons[i][j] << \" \";\n\t\t\t}\n\t\t\tstd::cout << std::endl;\n\t\t}\n\t}\n\n\tvoid pushNumbers(Numbers&#038; numbers) {\n\t\tpersons.push_back(numbers);\n\t}\n\n\tvoid pushCandidates(std::string&#038; name) {\n\t\tcandidates.push_back(name);\n\t\tvotes.push_back(0);\n\t}\n\n};\n\nint main() {\n\tAustralianVoting av;\n\tstd::string buffer;\n\tint numberOfCase;\n\tint numberOfCandidates;\n\tstd::cin >> numberOfCase;\n\tstd::getline(std::cin, buffer);\n\tfor (int i = 0; i < numberOfCase; ++i) {\n\t\tif (i != 0)\n\t\t\tstd::cout << std::endl;\n\t\tstd::cin >> numberOfCandidates;\n\t\t\/\/\t\tstd::cout<<\"numberOf Candidates : \"<<numberOfCandidates<<std::endl;\n\t\tstd::getline(std::cin, buffer);\n\t\tfor (int j = 0; j < numberOfCandidates; ++j) {\n\t\t\tstd::getline(std::cin, buffer);\n\t\t\tav.pushCandidates(buffer);\n\t\t}\n\t\t\/\/\t\tstd::cout<<\"pushNames Done..\"<<std::endl;\n\n\t\tint emptyCounter = 0;\n\t\twhile (emptyCounter < 2) {\n\t\t\tstd::getline(std::cin, buffer);\n\t\t\tif (buffer.empty()) {\n\t\t\t\temptyCounter++;\n\t\t\t} else {\n\t\t\t\tNumbers nums;\n\t\t\t\tstd::istringstream iss(buffer);\n\n\t\t\t\tint num;\n\t\t\t\twhile (iss >> num) {\n\t\t\t\t\tnums.push_back(num - 1);\n\t\t\t\t}\n\t\t\t\t\/\/\t\t\t\tstd::cout<<\"nums size : \"<<nums.size()<<std::endl;\n\n\t\t\t\tav.pushNumbers(nums);\n\n\t\t\t}\n\t\t}\n\n\t\t\/\/\t\t\t\tav.printNumbers();\n\t\tav.vote();\n\t\tav.reset();\n\n\t}\n\n\treturn 0;\n}<\/pre>\n","protected":false},"excerpt":{"rendered":"<p>\ubb38\uc81c &lt;- \ud074\ub9ad \uc544.. \uc774\uac74 \ub610 \ubb50\uac00 \ubb38\uc81c\uc9c0&#8230;? \uccb4\uc2a4 \ubb38\uc81c \ucc98\ub7fc \ub098\uc911\uc5d0 \ub2e4\uc2dc\ubcf4\uba74 \ub610 \ub208\uc5d0 \ubcf4\uc774\uaca0\uc9c0. \uc2dc\uac04 \ub0ad\ube44\ub294 \ud558\uc9c0\ub9d0\uc790.. \ubc14\uc058\ub2e4! #include #include #include #include typedef std::vector Numbers; class AustralianVoting { std::vector candidates; std::vector persons; std::vector votes; std::vector eliminated; bool checkMoreVotes() { int max = 0; std::vector::iterator it; for (it = votes.begin(); it != votes.end(); ++it) [&hellip;]<\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"spay_email":""},"categories":[9],"tags":[49,59,203,280,385,452,471],"jetpack_featured_media_url":"","jetpack_sharing_enabled":true,"jetpack_shortlink":"https:\/\/wp.me\/pXV5a-A7","_links":{"self":[{"href":"https:\/\/talsu.net\/index.php?rest_route=\/wp\/v2\/posts\/2239"}],"collection":[{"href":"https:\/\/talsu.net\/index.php?rest_route=\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/talsu.net\/index.php?rest_route=\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/talsu.net\/index.php?rest_route=\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/talsu.net\/index.php?rest_route=%2Fwp%2Fv2%2Fcomments&post=2239"}],"version-history":[{"count":0,"href":"https:\/\/talsu.net\/index.php?rest_route=\/wp\/v2\/posts\/2239\/revisions"}],"wp:attachment":[{"href":"https:\/\/talsu.net\/index.php?rest_route=%2Fwp%2Fv2%2Fmedia&parent=2239"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/talsu.net\/index.php?rest_route=%2Fwp%2Fv2%2Fcategories&post=2239"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/talsu.net\/index.php?rest_route=%2Fwp%2Fv2%2Ftags&post=2239"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}