[알고리즘] 백준 1713

문제


반장선거를 하는데 N개의 후보군만 올라갈수있고 투표수가 적고 오래된 후보를 내리면서 새로운 후보를 올리는 문제다.

간단하게 array를 돌면서 체크하면 될거같았는데 문제는 시간이었다.
투표수가 동일하다면 가장 오래된 후보를 내려한다.
deque로 구현하면 될거같은 생각이 들었다.

근데 평소에 안써봐서 굳이 써야하나 싶다가 단순히 시간을 저장해봤다.
그외에 방법으로는 현재 인덱스 위치를 저장하는 방법도 있을듯싶다.

code

// 1713.cpp : 이 파일에는 'main' 함수가 포함됩니다. 거기서 프로그램 실행이 시작되고 종료됩니다.
//

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

vector<vector<int>> cands; // vote, time, idx

bool compare(vector<int> a, vector<int> b) {
    return a[2] < b[2];
}

int main(){
    int N;
    int num;
    int time = 0;
    cin >> N;
    cin >> num;
    while (num--) {
        time++;
        int cand;
        //cin >> cand;
        scanf("%d", &cand);
        // 이미 있으면 더해주기
        bool isAleady = false;
        for (int i = 0; i < cands.size(); i++) {
            if (cands[i][2] == cand) {
                cands[i][0]++;
                isAleady = true;
            }
        }
        if (isAleady) continue;

        // 후보군이 여유있으면 넣기
        if (cands.size() < N) {
            cands.push_back({ 1,time, cand });
            continue;
        }
        // 후보군이 여유없으면 가장 작은 투표중 오래된거 내보내기
        sort(cands.begin(), cands.end());
        cands[0] = { 1,time,cand };
    }
    // 순서 정렬
    sort(cands.begin(), cands.end(), compare);
    // 출력
    for (int i = 0; i < cands.size(); i++) {
        cout << cands[i][2] << " ";
    }
}

좋은 웹페이지 즐겨찾기