[백준] 1713번 후보추천하기

후보를 주어진 조건에 알맞게 sort시키는 문제이다. sort의 방식을 잘 생각해보자

문제

---

힌트

문제에서 필자가 찾지 못했던 부분은 조건 2번과 조건 3번을 고려를 잘해야한다. 개인적으로는 조건 2번에서 틀리는 경우보다는 조건 3번에서 틀리는 경우가 더 많을 거라고 생각하는데 3번째 조건을 잘 봐주면 생각보다 쉽게 풀리는 문제였다. 추가로 후보자가 주어진 n명보다 적게 나오는 경우를 고려해서 출력하길 바란다. 필자는 그부분을 고려를 못해서 삽질을…

코드 자세히 보기

#include <iostream>
#include <queue>
#include <algorithm>
using namespace std;
class student // 후보 구조체 사용
{
    public:
    int num;
    int count;
    int time;
};
bool comp(student a, student b) // 정렬을 위한 comp
{
    if(a.count == b.count)
        return a.time > b.time;
    return a.count > b.count;
}
int main(void)
{
    cin.tie(NULL);
    cout.tie(NULL);
    ios::sync_with_stdio(false);
    int n;
    int t;
    cin >> n;
    cin >> t;
    vector<student> photo;
    vector<int> num(105, 0); //중복확인
    vector<int> ans; 
    for(int i = 0; i < t; i++)
    {
        int vote;
        cin >> vote;
        if(num[vote] != 0)
        {
            for(int j = 0; j < n; j++)
            {
                if(photo[j].num == vote)
                {
                    photo[j].count++;
                }
            }
        }
        else
        {
            if(photo.size() == n)
            {
                num[photo.back().num] = 0;
                photo.pop_back();
            }
            photo.push_back({vote, 1, i});
        }
        num[vote]++;
        sort(photo.begin(), photo.end(), comp);
    }
        for(int i = 0; i < photo.size(); i++)
            ans.push_back(photo[i].num);
        sort(ans.begin(), ans.end());
        for(int ans: ans)
            cout << ans << " ";
        cout << endl;
}

---

문제 풀이

이번 문제에서는 class나 구조체의 구성을 어떻게 이루고, 그 구성을 sort시킬 때의 방식을 잘 활용하면 풀 수 있는 문제였다. 특히 조건 3번을 위해 student class에 times라는 변수를 추가해주는 것이 중요했다고 생각한다.

문제 결과

문제 출처 https://www.acmicpc.net/problem/1713