결선투표

이전 과제인 Plurality에서 시뮬레이션한 다수결 투표는 모든 투표자가 한 표씩 행사할 수 있고 가장 많은 표를 얻은 후보자가 당선되는 시스템이었다. 하지만 다수결 투표는 몇 가지 문제가 있다. 예를 들어 Alice, Bob, Charlie 세 명의 후보가 있고 각각 2표, 2표, 1표를 받았다고 한다면 승자는 Alice와 Bob이 된다. 이것은 좋은 결과라고 할 수 있을까?


이에 대한 대안으로 순위선택투표 시스템이 있다. 투표자는 가장 선호하는 한 명의 후보자가 아닌, 여러 명의 후보자를 선호 순위에 따라 선택할 수 있다. 동점자가 발생했을 경우, 최저 득표를 한 후보자를 제거한 뒤 그 후보자를 선택한 투표자가 차선으로 선택한 후보자에게 그 표를 이동시켜 결선을 치루는 방식이다.

선택순위투표는 다수결 투표의 또 다른 잠재적인 결함을 보완해준다. Alice, Bob, Charlie 세 명의 후보에 대해 9명이 투표한 결과 각각 2표, 3표, 4표를 얻었다고 했을 때, 다수결 투표에 따르면 승자는 Charlie가 된다. 하지만 Alice와 Bob을 뽑은 과반수인 5명에게는 Charlie가 최악의 선택이었다고 한다면, Charlie의 당선은 합리적인 결과라고 할 수 있을까?

선택순위투표 시스템 중 하나인 ‘즉각 결선 투표’는 이러한 한계를 보완해준다. 투표자는 원하는 만큼 후보자의 선호 순위를 정할 수 있고, 만약 한 후보자가 과반수 득표를 한다면 승리하게 된다. 만약 과반수를 얻은 후보자가 없다면 ‘즉각 결선’이 이루어진다. 가장 적은 득표를 한 후보자는 탈락하고, 대신 차선으로 뽑힌 후보자가 그 자리를 대신하게 된다. 당선자가 나올 때까지 이 과정을 반복한다.


우리가 고려해야 할 특수 케이스가 남아있다. 최저 득표를 한 후보자가 여러 명인 경우이다. 이 때는 동점자를 모두 제거하면 될 것이다. 하지만 모든 후보자가 똑같은 득표수를 갖는 경우에는, 후보자 전체를 제거하지 않도록 주의해야 한다.

또한 실제 선택순위투표 시스템에서는 투표자가 모든 순위를 채우지 않아도 되는 경우가 있지만, 이 프로그램에서는 투표자가 모든 후보자에 대해 순위를 매겨야 한다고 가정한다.

Runoff 과제

아래 예시와 같이 동작하는 투표 프로그램을 작성한다.

./runoff Alice Bob Charlie
Number of voters: 5
Rank 1: Alice
Rank 2: Charlie
Rank 3: Bob

Rank 1: Alice
Rank 2: Charlie
Rank 3: Bob

Rank 1: Bob
Rank 2: Charlie
Rank 3: Alice

Rank 1: Bob
Rank 2: Charlie
Rank 3: Alice

Rank 1: Charlie
Rank 2: Alice
Rank 3: Bob

Alice

과제용 뼈대 코드

• 두 상수가 정의되어 있다. MAX_CANDIDATES는 투표 입후보자의 최대 인원, MAX_VOTERS는 투표자의 최대 인원을 의미한다.
• 2차원 배열인 preferences가 정의되어 있다. preferences[i]는 i번 투표자를 나타내고, preferences[i][j]는 i번 투표자가 j번째로 선호하는 후보자의 인덱스를 저장할 것이다.
• candidate 구조체가 정의되어 있다. 각 candidate은 자신의 이름을 저장하는 string 타입의 name, 득표수를 저장하는 int 타입의 votes, 그리고 경선에서 제외되었는지 여부를 저장하는 bool 타입의 eliminated 세 가지 필드를 가진다. candidates 배열은 각 candidate에 대한 정보를 저장한다.
• 두 가지 전역 변수 voter_count와 candidate_count가 정의되어 있다.
• Main 함수에서, candidate_count와 voter_count를 결정한 뒤 모든 투표자에게 투표 기회를 주는 루프가 실행된다. 선호 순위를 저장하기 위해 vote 함수가 호출되며, 만약 어떠한 이유로 투표가 유효하지 않다고 판단되면 프로그램을 종료한다.
• 투표 루프가 종료되면, 결선 과정을 통해 최종 승자를 결정하는 루프가 실행된다.
• 여기서 처음 실행되는 함수는 tabulate이다. 각 투표자가 가장 선호하는 후보자를 집계하여 현재의 총 득표수를 계산한다. 아직은 후보자를 제거하지 않는다. 그 다음으로는 print_winner가 승자를 출력한다. 만약 승자가 1명이라면 프로그램을 종료한다. 그렇지 않다면 find_min을 호출해 최저 득표수를 계산해야 한다. 만약 is_tie 함수를 호출하여 모든 후보자가 동점이라면 투표는 무승부가 된다. 그렇지 않다면 eliminate 함수를 호출하여 최저 득표를 한 후보자를 제거한다.
• 파일의 아랫쪽에 있는 vote, tabulate, print_winner, find_min, is_tie, eliminate 함수를 완성한다.

지시사항

runoff.c의 기존 코드에서 vote, tabulate, print_winner, find_min, is_tie, eliminate 함수 외에는 수정해서는 안된다. 헤더 파일 추가는 가능하다.

Vote

• voter, rank, name을 인수로 받는다.
• name은 후보자의 이름을 의미한다. voter가 선택한 rank에 맞게 preferences 배열 변수를 업데이트한다.
• 선호 순위가 성공적으로 저장되면 함수는 true를 반환한다. 그렇지 않다면 false를 반환한다(name에 맞는 후보자의 이름이 없는 경우 등).
• 후보자의 이름은 다른 후보자와 중복되지 않는다고 가정한다.

tabulate

• 해당 경선 단계에서 각 후보자의 득표수를 계산한다.
• 각 경선 단계에서 투표자는 제거되지 않은 후보들 중 가장 선호하는 후보자에게 투표하게 된다.

print_winner

• 만약 과반수의 표를 얻은 후보자가 있다면, 후보자의 이름을 stdout으로 출력하고 true를 반환한다.
• 만약 어떤 후보자도 승리하지 못했다면 false를 반환한다.

find_min

• 해당 경선 단계에 남아있는 후보자들의 득표수 중 가장 적은 값을 찾는다.

is_tie

• 해당 경선 단계에 남아있는 후보자들의 득표수 중 가장 적은 값인 min을 인수로 받는다.
• 해당 경선 단계에 남아있는 후보자들이 모두 동일한 득표수를 갖는다면 true를 반환하고, 그렇지 않다면 false를 반환한다.

eleminate

• 해당 경선 단계에 남아있는 후보자들의 득표수 중 가장 적은 값인 min을 인수로 받는다.
• min 값을 가진 후보자를 제거한다(둘 이상이 될 수도 있다).

✍️ 풀이

vote()

voter(사용자)에게 입후보자의 이름을 입력받은 뒤 즉시 호출되어 유효한 값인지 체크하는 함수. 유효한 값이면 preferences(투표 용지)에 저장한 뒤 true를 반환한다. 유효하지 않으면 false를 반환하고, 값을 받은 main은 프로그램을 종료한다.

bool vote(int voter, int rank, string name)
{
    for (int i = 0; i < candidate_count; i++)
    {
        if (strcmp(name, candidates[i].name) == 0)
        {
            preferences[voter][rank] = i;
            return true;
        }
    }

    return false;
}

tabulate()

모든 투표자의 기명이 완료된 뒤 호출되어 해당 경선의 투표 결과를 계산한다. 선택순위투표 시스템에 따라 득표수를 계산하여 candidates.votes를 업데이트한다.

void tabulate(void)
{
    for (int i = 0; i < voter_count; i++)
    {
        for (int j = 0; j < candidate_count; j++)
        {
            int index = preferences[i][j];

            if (candidates[index].eliminated == false)
            {
                candidates[index].votes++;
                break;
            }
        }
    }

    return;
}

print_winner()

과반수의 득표를 얻은 승자가 있는지 판단하여, 있다면 승자의 이름을 출력한 뒤 true를 반환하고, 없다면 false를 반환한다. main은 true값을 받은 경우 프로그램을 종료한다.

bool print_winner(void)
{
    for (int i = 0; i < candidate_count; i++)
    {
        if (candidates[i].votes > voter_count / 2)
        {
            printf("%s\n", candidates[i].name);
            return true;
        }
    }

    return false;
}

find_min()

최저 득표자를 제거하기 위해 최저 득표수를 구한다.

int find_min(void)
{
    int min = voter_count;

    for (int i = 0; i < candidate_count; i++)
    {
        if (candidates[i].eliminated == false && candidates[i].votes < min)
        {
            min = candidates[i].votes;
        }
    }

    return min;

is_tie()

해당 단계에 남아있는 후보자들이 모두 동점인지 판단한다. 동점인 경우 true를 반환하고, 그렇지 않다면 false를 반환한다. main은 true를 받은 경우 제거되지 않은 후보들의 이름을 차례로 출력한 뒤 프로그램을 종료한다.

bool is_tie(int min)
{
    for (int i = 0; i < candidate_count; i++)
    {
        if (candidates[i].eliminated == false && candidates[i].votes != min)
        {
            return false;
        }
    }

    return true;
}

eliminate()

과반수의 득표를 얻은 승자가 없고 남아있는 모든 후보자가 동점이 아니라면 eliminate()가 호출되어 최저 득표를 한 후보자를 제거한다.

void eliminate(int min)
{
    for (int i = 0; i < candidate_count; i++)
    {
        if (candidates[i].votes == min)
        {
            candidates[i].eliminated = true;
        }
    }

    return;
}

✍️ 메모

요구사항 이해하기

무작정 코드를 쓰기 전에 무엇을 구현해야 하는지 잘 이해하는 것이 중요하다고 느꼈다. 생존한 후보들이 모두 동점인지 여부를 판단하는 is_tie() 코드를 처음 작성했을 때, 나는 곧이곧대로 이해했다. 생존한 후보의 수와 최저 득표수를 가진 후보수를 카운트 한 뒤 두 값이 같으면 true를 반환하도록 했다. 하지만 요구조건을 달리 생각해본다면, 생존한 후보가 최저 득표수가 아닌(혹은 그보다 큰) 값을 가지고 있다면 is_tie()는 false를 반환하면 된다. 카운트 코드는 불필요하다.

---

Reference

• CS50 Fall 2019 Problem set 3 Runoff