문제
N명이 3명의 후보에게 1~3점으로 투표한다. 가중 합계가 가장 높은 후보가 당선되며, 동점이면 3점 득표 수, 2점 득표 수 순으로 비교한다. 끝까지 같으면 0을 출력한다.
입력
첫째 줄에 학생 수 N, 이후 N줄에 각 학생이 1, 2, 3번 후보에게 준 점수가 주어진다.
출력
당선자 번호와 최고 점수를 출력한다.
예제
| 입력 | 출력 |
|---|---|
5 3 2 1 2 1 3 3 1 2 1 2 3 2 3 1 | 1 11 |
풀이
각 후보별 득표를 집계하고 다중 조건으로 당선자를 결정한다.
- 각 후보별 1점, 2점, 3점 득표 수를 배열에 기록한다
- 가중 합계(1×1점수 + 2×2점수 + 3×3점수)를 계산한다
- 최고 점수 후보를 찾되, 동점이면 3점 득표 수 → 2점 득표 수 순으로 비교한다
- 모든 기준에서 같으면 0과 최고 점수를 출력한다
핵심 아이디어: 다중 우선순위 비교(가중합 → 3점수 → 2점수)로 타이브레이크를 처리하며, 3명 고정이므로 O(N)에 해결된다.
코드
#include <iostream>
using namespace std;
int score[3][4];
int main()
{
cin.tie(NULL);
ios_base::sync_with_stdio(false);
int n;
cin >> n;
for (int i = 0; i < n; i++)
{
int f, s, t;
cin >> f >> s >> t;
score[0][f - 1]++;
score[1][s - 1]++;
score[2][t - 1]++;
}
int idx = -1, max = 0;
bool check = false;
for (int i = 0; i < 3; i++)
{
score[i][3] = score[i][0] * 1 + score[i][1] * 2 + score[i][2] * 3;
if (max < score[i][3])
{
max = score[i][3];
idx = i;
check = true;
}
else if (max == score[i][3])
{
if (score[idx][0] < score[i][0])
{
idx = i;
check = true;
}
else if (score[idx][0] == score[i][0] && score[idx][1] < score[i][1])
{
idx = i;
check = true;
}
else if (score[idx][0] == score[i][0] && score[idx][1] == score[i][1])
{
check = false;
}
}
}
if (check == false)
idx = -1;
cout << idx + 1 << " " << max;
return 0;
}복잡도
- 시간: O(N)
- 공간: O(1)