[알고리즘 트레이닝 북] 8번 호주식 투표법
문제 설명
이번 문제는 호주식 투표법을 구현하는 문제이다. 호주식 투표법은 투표를 할 때, 모든 후보를 순위를 매겨 투표를 한 후, 과반수가 1순위 후보로 한 후보를 뽑으면 그 후보가 선출되고, 아니면 1순위로 가장 적은 표를 받은 후보를 탈락시키고 그 후보를 1순위로 뽑은 표들을 모아 2순위로 찍은 후보의 표로 간주하여 다시 집계한다. 이 때에도 과반수의 표를 받은 후보가 없으면 똑같은 방식으로 가장 적은 표를 얻은 후보에게 던진 표들을 다음 순위에 쓰여 있는 후보의 표로 간주하여 다시 집계하고… 이렇게 하다 보면 두 가지 결과가 나오는 데, 특정 후보가 과반수의 표를 받아 선출되거나, 남은 모든 후보의 득표 수가 동일하여 선출이 불가능한 경우이다.
입력은 후보의 수를 먼저 입력하고, 후보의 이름이 그 수만큼 입력된 후 투표지 수는 입력되지 않고 바로 투표가 입력된다. 투표는 후보의 번호 (입력된 순서대로)를 공백으로 구분하여 (ex. 3 1 2) 입력하는 형태이다. 공백인 상태로 개행이 입력되면 투표가 끝난 것으로 간주한다.
풀어 보기
1. 큰 그림 그리기
- 후보 수와 후보 이름을 입력받아 저장한다.
- 투표: 개행 입력시까지 아래를 반복한다.
- 투표지를 하나 새로 만든다
- 투표지에 입력을 받는다
- 아무것도 입력안되면 break
- 개표: 과반수 후보 나올 때까지 아래를 반복한다.
- 집계한다
- 과반수 득표 후보 있으면 선출 (break)
- 모든 후보 득표 수 같으면 개표 종료 (break)
- 없으면 탈락시킬 가장 적은 표 받은 후보 찾아 탈락시킨다
- 선출: 개표에서 나온 후보 번호에 맞는 후보 이름을 출력한다.
2. 투표용지와 후보들
우선 투표지를 어떤 형태로 받느냐를 생각해야 했다. 투표용지 한 장에는 모든 후보에 대한 순위를 저장해야 한다. 가장 먼저 떠오르는 것은 후보 수 * 투표용지 수 크기의 2차원 배열이다. 배열에는 해당 투표자의 n순위 후보의 번호가 저장되는 것이 가장 편리할 듯 하다. 후보의 이름 역시 후보의 번호를 기준으로 배열을 만들어 사용하였다.
int cand = 0;
cin >> cand; //후보 수 입력받음
char(*candName)[80] = new char[cand][80];
//후보 수만큼 80자씩 후보이름 메모리 동적할당
for (int i = 0; i < cand; i++)
cin >> candName[i];
//후보 수만큼 후보이름 입력받음
후보 이름은 최대 80자였으므로, 고정시키고 후보 수는 따로 입력을 받아 저장하므로 동적할당을 사용할 수 있었다. 전 문제에서 사용했던 포인터 배열을 사용하여 쉽게 해결할 수 있었다.
처리가 까다로웠던 것 중에 하나는 후보 수는 프로그램에서 입력이 되어지지만, 투표용지 수는 먼저 입력하지 않고 개행이 입력될 때 까지 계속 추가된다는 것이었다. 최대 1000개의 투표지가 입력되어서 1000개의 투표용지를 투표 전에 미리 만들까 했는데, 너무 낭비같아서 모범 답안과는 다르게 동적 할당을 사용할 방법을 고민하였다.
int * vote[1000];//vote는 투표결과를 저장할 포인터
우선 1000개의 인티저 포인터 배열을 만들고 각 포인터에 투표지를 투표지가 입력될 때 마다 동적으로 할당하기로 하였다.
cin.getline(temp, 40);
//투표지 만들고 입력받음
vote[vote_s] = new int[cand]; //새 투표지 할당
for (int i = 0; i < cand; i++)
vote[vote_s][i] = temp[2 * i] - 48;//ASCII코드 변환
vote_s++; //총 투표 수 1 증가
위의 코드를 투표결과를 입력받는 반복문 안에 넣었다. 투표용지 수가 최대 1000개이므로 포인터 1000개를 만든 후, 이중포인터를 투표가 입력될 때마다 새로 할당하였다. 투표용지의 길이는 후보 수와 같으므로 후보 수만큼 동적할당하였다. 1000*후보 수 만큼의 배열을 미리 만드는 것보다 메모리를 아낄 수 있었다. temp는 문자열이므로 중간에 공백을 제외하고 입력받은 문자를 integer형태로 변환하여 투표용지에 저장한다.
3. 개표와 선출, 탈락 후보 처리 문제
첫 집계를 하고, 과반수 득표가 있는지 검사한 후 없으면 탈락후보를 선정하는 것 까지는 어렵지 않게 할 수 있었다.
int * result = new int [cand];
for (int i = 0; i < cand; i++)
result[i] = 0;
result는 각 후보의 득표 수를 저장하는 변수이다.
int overfifty(int * result, int cand, int vote_s)
{//50퍼 넘는 후보 있으면 해당후보 배열번호를, 없으면 -1 반환
for (int i = 0; i < cand; i++)
if (result[i] > vote_s * 0.5)
return i;
return -1;
}
총 투표 수는 두 번째 집계 이후에도 변하지 않을 것이므로 투표수의 과반을 넘으면 해당 후보의 번호를 반환하는 함수 역시 쉽게 작성해 볼 수 있었다. 이 문제에서 가장 어려웠던 부분은 탈락한 후보를 어떻게 저장하고, 다음 개표에서 어떻게 구분하여 집계할 것인가의 문제였다.
처음에는 result에 첫 번째 집계 결과를 저장하고, 탈락한 후보를 찍은 표를 찾아 다음 순위로 찍은 후보로 표를 ‘이동’시키는 개념을 생각하고 있었다. 그러나, 구현이 굉장히 까다로웠다. 반면에 result에 득표 수를 집계하는 함수는 생각보다 매우 간단하게 구현되었다. 이에 따라, 탈락한 후보 번호만을 따로 저장한 후, 매 번 초기화 된 result에 표를 ‘다시 집계’하는 방향으로 생각하게 되었다.
int * countvote(int cand, int vote_s, int ** vote, bool * fail)
{
//한 표씩 개표
for (int i = 0; i < vote_s; i++)
{
for (int r = 0; r < cand; r++)
if (fail[vote[i][r]]) //r순위 후보가 탈락자면 다음 순위로
continue;
else
{//탈락자 아니면 result에 반영하고 break
result[vote[i][r] - 1]++;
break;
}
}
return result;
}
fail은 후보 수 만큼의 길이를 갖는 bool 배열로, true이면 해당 번호의 후보는 이미 탈락한 것이다. 이렇게 생각해두니 후보 탈락의 문제도 fail의 T/F값만 바꿔주면 되는 문제가 되어 별도의 간단한 함수로 구현할 수 있었다.
void whofail(int cand, int * result, bool * fail)
{//득표 수가 가장 낮은 후보를 찾아 탈락시킨다.
//가장 낮은 득표수를 저장할 fff변수
int fff;
for (int i = 0; i < cand; i++)
if (!fail[i])
{//탈락하지 않은 가장 번호 빠른 후보의 득표 수 저장
fff = result[i];
break;
}
//가장 낮은 득표수를 찾는다
for (int i = 0; i < cand; i++)
if (!fail[i] && fff < result[i])
fff = result[i];
//가장 낮은 득표수를 가진 후보들을 반복문으로 찾아 탈락시킴
for (int i = 0; i < cand; i++)
if (result[i] == fff)
fail[i] = true;
}
탈락 후보를 찾는 코드가 다소 길어진 이유는 두 후보가 동시에 탈락하는 경우 역시 문제에서 고려해야 했기 때문이다. 가장 낮은 득표수를 가진 후보가 여러명일 경우를 대비해 먼저 가장 낮은 득표 수를 찾고 해당 득표수를 가진 후보들에 대한 탈락 처리를 하였다. 모범 답안역시 비슷한 형태로 작성되었다. 다만, 후보를 탈락시키는 것을 득표 수를 ‘0’으로 바꾸는 것으로 처리하는 것이 달랐다. 처음에 내가 생각했던 방법인데 내가 굳이 fail 배열을 만들어 처리한 것은 첫 개표때 득표 수가 0일 경우 구분이 안되기 때문이었다. 그런데 생각해보니 구분이 될 필요가 없었다… 몇 번째 개표인지는 전혀 중요한 것이 아니기 때문에… 다만 후보가 선출되거나 모든 표 수가 같아질때까지 집계를 반복시키는 것이다.
while(1)
{
//집계
int * result = countvote(cand, vote_s, vote, fail);
//모두탈락하는 경우 = 후보들이 동률인 경우 : 개표종료
for (int i = 0; i < cand; i++)
if (!(fail[i]))
break;
else if (i == cand - 1)
return -1;
//50퍼 이상 후보 있는지 검사해서 있으면 선출끝
int elec = overfifty(result, cand, vote_s);
if (elec + 1)
return elec;
//50퍼 이상 후보 없으면 탈락시킬 후보 추가함
whofail(cand, result, fail);
}
전체적으로 이런 형태로 개표 부분을 구현할 수 있었다.
끝
처음에 과반수 득표 후보가 없으면 해당 후보에 투표한 투표지를 걸러내서 읽어 낼 ‘순위’를 바꿔서 그것들만 집계해서 수정한다는 flow를 가지고 하려니 굉장히 어려운 문제로 느껴졌다. 매 번 재집계를 하는 일이 무언가 낭비처럼 느껴졌는데 직접 구현해 보니 집계를 하는 함수가 복잡하지 않아 오히려 코드가 매우 간결해지고 집계와 탈락 후보 처리를 분리해서 생각할 수 있어 훨씬 쉽게 구현해 볼 수 있었다. 이렇게 기능을 분리해서 생각하는 것이 정말 중요한 것 같다는 생각을 해보며…
전체 코드는 github 에서 볼 수 있습니다.