[알고리즘] 백준 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] << " ";
}
}
Author And Source
이 문제에 관하여([알고리즘] 백준 1713), 우리는 이곳에서 더 많은 자료를 발견하고 링크를 클릭하여 보았다
https://velog.io/@shininghyunho/알고리즘-백준-1713
저자 귀속: 원작자 정보가 원작자 URL에 포함되어 있으며 저작권은 원작자 소유입니다.
우수한 개발자 콘텐츠 발견에 전념
(Collection and Share based on the CC Protocol.)
// 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] << " ";
}
}
Author And Source
이 문제에 관하여([알고리즘] 백준 1713), 우리는 이곳에서 더 많은 자료를 발견하고 링크를 클릭하여 보았다 https://velog.io/@shininghyunho/알고리즘-백준-1713저자 귀속: 원작자 정보가 원작자 URL에 포함되어 있으며 저작권은 원작자 소유입니다.
우수한 개발자 콘텐츠 발견에 전념 (Collection and Share based on the CC Protocol.)