[C언어 기출문제&풀이] 후보식 투표법(Australian Voting)

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

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

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

풀이: 주석을 일일이 달아놓았기 때문에 주석을 읽으면 이해할 수 있을 것이다.
 
소스코드
#include <stdio.h>
#include <string.h>

#define MAX_CANDIDATES 20 //후보자 수 제한  
#define MAX_VOTES 1000 // 투표자 제한 
#define MAX_NAME_LEN 80// 이름 길이 제한

void main(void)
{
 char name[MAX_CANDIDATES + 1][MAX_NAME_LEN +1]; // 이름
 char line[MAX_NAME_LEN + 1]; // 입력 받기 위한 변수
 int vote[MAX_VOTES][MAX_CANDIDATES]; //vote[i][j]는 i번째 투표자가 j번째로 선호하는 투표자
 int votes_won[MAX_CANDIDATES + 1]; // 후보자의 투표받은 수
 //index_of_1st_alive[i] = i번째 후보자가 가장 선호하는 사람
 int index_of_1st_alive[MAX_VOTES];
 
 int num_cases, num_cards, num_votes; //케이스 수,후보자 수,투표자 수
 int i,ptr,max_votes_won, min_votes_won;//(max,min)votes_won은 최고, 최소 득표자확인 
 int who_got_max,all_tied; //최고 득표수 후보자,동점 여부

 scanf("%d",&num_cases); // 입력 
 gets(line); // 개행

 while(num_cases-- > 0)
 {
  scanf("%d", &num_cards); //후보자 수 
  gets(line); // 개행
  for(i=1;i<=num_cards;i++)
  {
   gets(name[i]); // 후보자 이름 입력
   votes_won[i] = 0; // i번째 후보자의 득표수 0으로 초기화
  }
  num_votes = 0; //후보자 수 = 0
  while(gets(line)&&*line) //line이 NULL일때 까지 반복
  {
   ptr = 0; //
   for(i=0;i<num_cards;i++)
   {
    sscanf(line + ptr, "%d", &vote[num_votes][i]); //i번째 투표자의 투표 입력
    while( line[ptr] >= '0' && line[ptr] <='9')
     ptr++; // 다음 후보자수 입력 받기 위해 증가
    while(line[ptr] == ' ')
     ptr++; // 다음 후보자수 입력 받기 위해 증가
   }
    //num_votes번째의 투표자가 가장 선호하는 후보자의 투표수 증가
   votes_won[vote[num_votes][0]]++;
   //num_votes번째의 후보자가 가장 선호하는 사람을 첫번째로 초기화
   index_of_1st_alive[num_votes] = 0;
   num_votes++; //다음 투표의 입력을 위해 증가
  }
 }
 
 while(1)
 {
  max_votes_won = -1;
  min_votes_won = MAX_VOTES +1;
  all_tied = 1;

  for(i=1;i<=num_cards;i++)
  {
   if(votes_won[i] > 0)
   {
    if(votes_won[i] > max_votes_won) //i번째 후보자가 가장 많은 득표수를 얻었을 때
    {
     if(max_votes_won >= 0) //최고 득표수가 0이 아닐때
      all_tied = 0; //모든 후보자의 득표수는 동점이 아니다
     max_votes_won = votes_won[i]; //최고 득표수 입력
     who_got_max = i; //최고 득표한 후보자 번호 입력
    }
    if(votes_won[i] < min_votes_won) //i번째 후보자가 가장 적은 득표수를 얻었을때
    {
     if(min_votes_won <= MAX_VOTES)
      all_tied = 0;
     min_votes_won = votes_won[i];
    }
   }
  }
  //최고 득표수가 과반수를 넘거나 모든 후보자의 득표수가 동점일 때
  if(max_votes_won * 2 > num_votes || all_tied)
    break;

  for(i=0;i<num_votes;i++)
   //이 투표용지를 받은 후보자가 최소 득표자인가?
   if(votes_won[vote[i][index_of_1st_alive[i]]]==min_votes_won)
   {
    //선호 하는 후보자를 그 다음으로 선호하는 후보자로 지정 ;
    //투표용지를 받은 후보자가 최소 득표자가 아닐때 까지;
    //제일 선호하는 후보자를 그 다음으로 선호하는 후보자로 지정;
    for(index_of_1st_alive[i]++;votes_won[vote[i][index_of_1st_alive[i]]] <=min_votes_won;
    index_of_1st_alive[i]++) // 그 다음으로 선호하는 후보를 찾는다
     ;
    votes_won[vote[i][index_of_1st_alive[i]]]++;//후보에게 투표용지를 하나 추가
   }
   //최소 득표자들의 득표는 0으로 한다.
   for(i=1;i<=num_cards;i++)
    if(votes_won[i]==min_votes_won)
     votes_won[i]=0;
 }
 //과반 득표자가 있는 경우
 if(max_votes_won*2>num_votes)
  puts(name[who_got_max]);
 else
  //그렇지 않으면 살아남은 모든 후보자들을 출력
  for(i=1;i<=num_cards;i++)
   if(votes_won[i] > 0)
    puts(name[i]);
 if(num_cases >0)
  putchar('\n');
}