[BaeKJoon/C++] 백준 11637 c++ 인기투표

https://www.acmicpc.net/problem/11637

11637번: 인기 투표

문제

9694번 한신이는 당내 최고의원을 선출하기 위한 사전 인기투표의 결과를 받게 되었다.  하지만 공식 선거를 통해서 당내 최고의원이 되기 위해선 과반수의 표를 받아야 하기 때문에 현재의 인기투표 결과를 보고 본 최고의원 선거를 준비하려 한다. 한신이를 도와 누가 최고 득표자인지, 받은 투표수가 과반수 득표인지 아닌지를 빠르게 판단할 수 있도록 도와주자.

입력

맨 위 첫 번째 줄에 T(1 <T< 500)는 테스트 케이스 수를 의미한다. 각 테스트 케이스의 첫 번째 줄에는 n이 주어지고 n은 후보자 수를 의미하며, 다음 n 줄에는 순서대로 각 후보자가 받은 득표 수를 입력받는다.

후보자는 최소 2명에서 10명보다 많지 않으며, 득표 수는 50000표를 넘지 않으며, 후보자들은 분명 자기 자신을 찍기 때문에 최소 1표 이상은 받게된다.

출력

각 테스트 케이스는 첫 번째 줄부터 순서대로 출력된다. 최다 득표자가 과반수 득표를 했을 경우에는 "majority winner R", 절반 이하의 득표를 하였을 경우엔 "minority winner R"가 되며, 최다 득표자가 없을 때(최다 득표자가 1명 초과일 경우)  "no winner"를 출력한다. 이때 R은 최다 득표자의 후보자 번호를 의미하며, 후보자의 번호는 각 케이스에서 1, 2,... , n 으로 부여된다.

예제 입력 1 복사

4
3
10
21
10
3
20
10
10
3
10
10
10
4
15
15
15
45

예제 출력 1 복사

majority winner 2
minority winner 1
no winner
minority winner 4

코드

#include <iostream>
#include <vector>
#include <algorithm>    // sort, greater
 
using namespace std;
 
int main() {
 
    int test;
    cin>>test;
 
    for(int i=0; i<test; i++){
 
        int semi;
        cin>>semi;
 
        int max=0;
        int index;
        vector<int> vec;
 
        for(int i=1; i<=semi; i++){
            int n;
            cin>>n;
            vec.push_back(n);
 
            if(n>max){
                max=n;      // 최다 득표자
                index=i;    // 최다 득표자 배열 위치
            }
        }
 
        sort(vec.begin(), vec.end(), greater<int> ()); // 내림차순
        // ex) input 15, 16, 19, 45 grater-> 45, 19, 16, 15
        
        int cnt=0;
        int sum=0;
 
        for(int i=0; i<vec.size(); i++){
            if(vec[0]==vec[1]){     // 최다 득표자가 1명이 아니라 2명 이상일때,
            //ex) 45, 45, 16, 15
            //    0    1   2   3
                cnt++;              // 카운트
            }
            sum+=vec[i];
        }
        if(cnt==0){                 // 최다 득표자가 1명일때,
            if(sum-vec[0]<vec[0]){  // vec[0] = 최다 득표수
                                    // 최다 득표 수가 총 득표 수의 절반 이상을 차지할때,
                cout<<"majority winner "<<index<<"\n";
            }
            else if(sum-vec[0]>=vec[0]){ // 최다 득표 수가 총 득표수의 절반 이하일때,
                cout<<"minority winner "<<index<<"\n";
            }
        }
        else if(cnt>=1){            // 최다 득표자가 2명 이상일때,
            cout<<"no winner\n";     
        }
 
    }
    return 0;
}

입력받을 수를 내림차순 하여 최다 득표수가 총득표수의 절반 이상을 차지할 때, majority winner,

절반 이하일 때, minority winner, 여기까지는 쉬웠는데

최다 득표자가 1명이 아니라 2명 이상일 때가 많이 까다로웠다. 

그래서 많이 헤매다가 sort로 내림차순 해주고 vector 배열의 첫 번째 수와 두 번째 수가 같을 때 cnt로 카운트를 해서

cnt가 1 이상일 때의 뜻은 최다 득표수의 값이 2개 이상 같다는 뜻이니까

cnt>=1일 때는 최다 득표수가 절반 이상을 차지하든 이하를 차지하든 no winner로 출력해주었다.

 

실버 문제는 브론즈 문제에서 하나를 더 생각하게 하거나, 꼬는 부분에서 차이를 느꼈다.