[C++] 후보 추천하기 (1713번)

후보 추천하기

 

 

시간 제한메모리 제한제출정답맞힌 사람정답 비율

2 초

128 MB

14823

4287

3298

31.014%

문제

월드초등학교 학생회장 후보는 일정 기간 동안 전체 학생의 추천에 의하여 정해진 수만큼 선정된다. 그래서 학교 홈페이지에 추천받은 학생의 사진을 게시할 수 있는 사진틀을 후보의 수만큼 만들었다. 추천받은 학생의 사진을 사진틀에 게시하고 추천받은 횟수를 표시하는 규칙은 다음과 같다.

1. 학생들이 추천을 시작하기 전에 모든 사진틀은 비어있다.
2. 어떤 학생이 특정 학생을 추천하면, 추천받은 학생의 사진이 반드시 사진틀에 게시되어야 한다.
3. 비어있는 사진틀이 없는 경우에는 현재까지 추천 받은 횟수가 가장 적은 학생의 사진을 삭제하고, 그 자리에 새롭게 추천받은 학생의 사진을 게시한다. 이때, 현재까지 추천 받은 횟수가 가장 적은 학생이 두 명 이상일 경우에는 그러한 학생들 중 게시된 지 가장 오래된 사진을 삭제한다.
4. 현재 사진이 게시된 학생이 다른 학생의 추천을 받은 경우에는 추천받은 횟수만 증가시킨다.
5. 사진틀에 게시된 사진이 삭제되는 경우에는 해당 학생이 추천받은 횟수는 0으로 바뀐다.

후보의 수 즉, 사진틀의 개수와 전체 학생의 추천 결과가 추천받은 순서대로 주어졌을 때, 최종 후보가 누구인지 결정하는 프로그램을 작성하시오.

입력

첫째 줄에는 사진틀의 개수 N이 주어진다. (1 ≤ N ≤ 20) 둘째 줄에는 전체 학생의 총 추천 횟수가 주어지고, 셋째 줄에는 추천받은 학생을 나타내는 번호가 빈 칸을 사이에 두고 추천받은 순서대로 주어진다. 총 추천 횟수는 1,000번 이하이며 학생을 나타내는 번호는 1부터 100까지의 자연수이다.

출력

사진틀에 사진이 게재된 최종 후보의 학생 번호를 증가하는 순서대로 출력한다.

 

---

문제풀이

 

처음 생각났던 방법은 stable_sort를 이용하여 푸는 방법이었다.

사진틀(벡터)에 값을 넣고, 만약 사진틀이 모두 차서 한명 빼고 넣어야 하는 경우 stable_sort를 한 뒤 맨 앞의 값을 빼주고 맨 뒤에 값을 넣는 방법을 떠올렸다.

하지만 이렇게 하면 중간에 추천수가 더 오르는 경우가 있어 정렬로 인해 순서가 뒤바뀔 수 있다. 예를들어 처음 2 3 이렇게 있고 각각 추천을 5 4 받았을 경우 정렬하면 3 2 로 바뀐다. 이후 2가 추천을 받아 둘다 추천 수가 5 5 가 돠면 순서가 뒤바뀌게 되는 것이다. 이 문제 때문에 다른 방법으로 접근해 보았다.

 

값이 크지않아 그냥 반복문 돌면서 찾아주면 되는 것이었다.

 

구현 조건 분기는 다음과 같다.

사진틀에 이미 값이 들어있는 경우 -> 해당 값 추천수 1 증가.

들어있지 않은경우는 2개로 분기한다.

1. 그림틀 개수보다 적게 등록된 경우 -> 벡터에 값 푸쉬

2. 그림틀 개수보다 같거나 많이 등록된 경우 -> 추천수 제일 작은 학생 찾아서 삭제 후 백터에 값 푸쉬

 

이렇게 나누어 구현하면 의외로 실버 1 치고 간단하다.

 

#include <iostream>
#include <algorithm>
#include <vector>

using namespace std;

bool cmp(pair<int, int>& a, pair<int, int>& b) {
    if(a.second < b.second)
        return true;
    return false;
}

int main() {
    int n, m;
    cin >> n >> m;
    // 추천수, 학생번호
    vector<pair<int, int>> v;
    for(int i=0; i<m; i++) {
        int c;
        cin >> c;
        bool check = true;
        // vector에 값이 이미 들어가 있는 경우를 찾음
        for(int j=0; j<v.size(); j++) {
            if(v[j].second == c) {
                v[j].first++;
                check = false;
                break;
            }
        }

        // vector에 값이 들어가 있지 않은 경우
        if(check) {
            // 등록된 그림수 보다 vector의 사이즈가 작은경우
            if(v.size() < n) {
                v.push_back({1, c});
            }
            // 등록된 그림수 보다 vector의 사이즈가 크거나 같은경우
            else {
                int mini = 9999999;
                int idx = 9999;
                // 가장 추천수가 작은 늦게 들어온 학생을 찾는다.
                for(int j=0; j<v.size(); j++) {
                    if(v[j].first < mini) {
                        mini = v[j].first;
                        idx = j;
                    }
                }
                v.erase(v.begin() + idx);
                v.push_back({1, c});
            }
        }
    }

    sort(v.begin(), v.end(), cmp);
    for(int i=0; i<v.size(); i++)
        cout << v[i].second << " ";

    return 0;
}