1. 문제소개
1-1. 요구사항
- 후보는 추천을 받으면 사진틀에 들어감
- 이미 사진틀에 있다면 추천수가 하나 올라가고 없다면, 가장 추천 수가 낮은 사진위치에 들어감
- 이 때, 추천수가 동일하면 가장 오래 된 후보자 사진 위치에 들어감
- 사진틀의 개수와 전체 학생의 추천결과가 추천받은 순서대로 주어졌을 때, 최종 후보가 누구인지 결정해야함
1-2. 입력값과 출력값
//예제 입력
3 //사진의 갯수
9 //전체 추천 횟수
2 1 4 3 5 6 2 7 2 //추천 받는 번호
//예제 출력
2 6 7 //최종 후보들 번호
- 첫째 줄에 사진틀에 들어갈 수 있는 사진의 갯수가 주어짐
- 둘째 줄에 전체 추천 횟수가 주어짐
- 셋째 줄에 전체 학생의 추천결과가 순서대로 주어짐
1-3. 문제조건
- 사진틀의 갯수 N (1 <= N <= 20)
- 총 추천 횟수는 1000번 이하
- 학생들을 나타내는 번호는 1 ~ 100
2.문제풀이
2-1. 준비물
- 후보자들의 정보를 index로 하는 추천수 배열- (정적배열 : votes[101])
int votes[101]; // 1번 부터 100번까지의 학생이 있으므로 101짜리 배열을 선언한다.
- 후보자를 등록할 때, 2가지 정보가 필요함. 후보자의 번호와 후보자가 등록된 시간을 기록해야함
- 후보자의 번호를 first, 후보자가 처음으로 등록된 시간을 second로 넣을 수 있어야함
- 사진틀의 갯수 N만큼 vector의 사이즈를 동적으로 지정하고 vector의 자료형은 pair<int, int>를 사용
- 마지막에 순서대로 출력해야 하므로 결과를 담아줄 res vector를 선언
cin >> N >> M;
vector<pair<int, int>> v(N);
vector<int> res;
- int N : 사진틀의 칸수
- int M : 전체 추천의 갯수
- bool done : 사진틀이 비어있거나, 이미 존재하는 경우 done을 true로 변경하여 전체 탐색을 멈추게 할 변수
- int num : 추천받은 후보자 번호
int N, M, num;
bool done;
2-2. 풀이방법
- 총 M번 반복문을 가장 바깥에서 동작시킴
- 이 때 num 을 받아서 votes에 해당 인덱스 부분을 증가시킴
- 그리고 2개의 N 번 반복문을 이 안에서 작성함
- 첫 번째 반복문은 사진틀이 비었거나 추천받은 후보가 사진틀에 이미 존재하는 경우
- 두 번째 반복문은 추천받은 후보가 사진틀에 없어서 사진을 갈아야 하는 경우
- 1) 사진틀이 비어있거나 추천 받은 후보가 이미 있는 경우
if (v[j].first == 0)
{
v[j].first = num;
v[j].second = i;
done = true;
break;
}
else if (v[j].first == num)
{
done = true;
break;
}
- 2) 사진틀이 가득찼지만 추천 받은 후보가 없어서 한 칸을 비우고 넣어줘야 하는 경우
if (!done)
{
int index = 0;
for (int j = 1; j < N; j++)
{
if (votes[v[index].first] > votes[v[j].first])
index = j;
else if (votes[v[index].first] == votes[v[j].first])
{
if (v[index].second > v[j].second)
index = j;
}
}
votes[v[index].first] = 0;
v[index].first = num;
v[index].second = i;
}
- 위 과정이 끝나면 res 벡터에 v 벡터의 first 값을 push back 해주고
- sorting 후 하나씩 출력하면 끝
3.코드설명
3-1. 전체 구조
- 변수선언부, M번 반복 1번과 그 안에 N번 반복 2개, 결과값 정렬, 결과값 출력으로 구성
#include <iostream>
#include <vector>
#include <algorithm>
#define fast ios::sync_with_stdio(false), cin.tie(NULL), cout.tie(NULL);
using namespace std;
int votes[101];
int main()
{
fast;
int N, M, num;
bool done;
cin >> N >> M;
vector<pair<int, int>> v(N);
vector<int> res;
// 변수 선언
for (int i = 0; i < M; i++)
{
cin >> num;
votes[num]++;
done = false;
for (int j = 0; j < N; j++)
{
}
// 위 for문에서 조건이 만족하면 done이 true가 됨
if (!done)
{
int index = 0; // 바꿔줄 사진을 찾는 index
for (int j = 1; j < N; j++)
{
}
votes[v[index].first] = 0;
v[index].first = num;
v[index].second = i;
// 사진을 갈아 끼웠을 경우 이전 학생 투표 0
// 사진틀에 num으로 새 학생 갱신
// 그 학생이 들어온 순서 i를 second로 갱신
}
}
// 전체 큰 반복문 안에 조건에 따른 반복문 2개
for (int i = 0; i < N; i++)
res.push_back(v[i].first);
sort(res.begin(), res.end());
// 결과 벡터에 v벡터 first 값 하나씩 넣어주기
// 이후 정렬
for (int i = 0; i < res.size(); i++)
{
if (res[i] != 0)
cout << res[i] << ' ';
}
// 하나씩 출력
}
3-2. 변수선언부
// 전역변수
int votes[101] // 1번부터 100번 학생의 투표 수가 들어갈 것
/*==================*/
int N, M, num;
bool done;
cin >> N >> M;
vector<pair<int, int>> v(N);
vector<int> res;
3-3. M번 반복 for 문
- num 을 입력받고, 해당 학생 투표수 1 늘리고 done을 false 로 초기화한다.
for (int i = 0; i < M; i++)
{
cin >> num; // num 입력받음
votes[num]++; // num번째 학생이 추천을 받은 것이므로 추천 수 증가
done = false; // done은 매번 Fasle로 초기화
for (int j = 0; j < N; j++)
{
}
if (!done)
{
int index = 0;
for (int j = 1; j < N; j++)
{
}
}
}
3-3_1. N번 반복 for 문 (사진틀이 비어있거나 이미 사진틀에 존재한 후보인 경우)
for (int j = 0; j < N; j++)
{
if (v[j].first == 0) // 처음 순회하면서 v의 first값이 0 이면 사진틀이 비어있음
{
v[j].first = num; // 그 위치에 후보 등록
v[j].second = i; // 그 후보자의 등록 순서 입력
done = true; // done을 true로 설정
break; // 반복문 탈출
}
else if (v[j].first == num) // 만약 사진틀이 비어있지는 않았지만
{ // 사진틀에 해당 후보가 있는 경우
done = true; // done을 true로 설정
break; // 반복문 탈출
}
}
3-3_2. N번 반복 for 문 (사진틀이 가득 차있고 후보자를 갱신해야 하는 경우)
if (!done) //done이 false 일 때만 동작함
{
int index = 0; //우리가 바꿔줄 사진틀의 index
for (int j = 1; j < N; j++)
{
if (votes[v[index].first] > votes[v[j].first]) //투표수가 가장 적은 사람 찾는 로직
index = j; // 투표수가 작은 것으로 갱신
else if (votes[v[index].first] == votes[v[j].first]) //투표수가 동일할 경우
{ // 이 조건에 들어옴
if (v[index].second > v[j].second)
index = j; // 더 오래된 사진의 인덱스로 갱신
}
}
votes[v[index].first] = 0; // 반복이 끝나고 바뀌기로 정해진 인덱스의 후보자 투표수 0
v[index].first = num; // 새로 바뀐 사진의 번호 num
v[index].second = i; // 새로 바뀐 사진의 들어온 순서 i
}
4.전체 소스 코드
#include <iostream>
#include <vector>
#include <algorithm>
#define fast ios::sync_with_stdio(false), cin.tie(NULL), cout.tie(NULL);
using namespace std;
int votes[101];
int main()
{
fast;
int N, M, num;
bool done;
cin >> N >> M;
vector<pair<int, int>> v(N);
vector<int> res;
for (int i = 0; i < M; i++)
{
cin >> num;
votes[num]++;
done = false;
for (int j = 0; j < N; j++)
{
if (v[j].first == 0)
{
v[j].first = num;
v[j].second = i;
done = true;
break;
}
else if (v[j].first == num)
{
done = true;
break;
}
}
if (!done)
{
int index = 0;
for (int j = 1; j < N; j++)
{
if (votes[v[index].first] > votes[v[j].first])
index = j;
else if (votes[v[index].first] == votes[v[j].first])
{
if (v[index].second > v[j].second)
index = j;
}
}
votes[v[index].first] = 0;
v[index].first = num;
v[index].second = i;
}
}
for (int i = 0; i < N; i++)
res.push_back(v[i].first);
sort(res.begin(), res.end());
for (int i = 0; i < res.size(); i++)
{
if (res[i] != 0)
cout << res[i] << ' ';
}
}
