[Algorithm]Baekjoon 1813번 : 후보 추천하기

https://www.acmicpc.net/problem/1713

 

#include <iostream>
#include <string>
#include <map>
#include <vector>
#include <algorithm>
#include <math.h>
#include <queue>
#include <functional>
#include <sstream>
#include <memory.h>
#include <deque>
#include <set>
 
using namespace std;
 
struct Node
{
    int num;
    int date;
};
 
int n, m, num;
int recommendationCounts[101] = { 0 };
vector<Node> frames;
bool isInFrames[101] = { false };
 
bool cmp(const Node& a, const Node& b)
{
    if (recommendationCounts[a.num] == recommendationCounts[b.num]) // 추천횟수같으면
    {
        return a.date > b.date;
    }
 
    return recommendationCounts[a.num] > recommendationCounts[b.num];
}
 
bool cmp1(const Node& a, const Node& b)
{
    return a.num < b.num;
}
 
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
 
    cin >> n >> m;
 
    for (int i = 0; i < m; ++i)
    {
        cin >> num;
 
        ++recommendationCounts[num];
 
        if (!isInFrames[num])
        {
            if (frames.size() == n) // 꽉찼을경우
            {
                sort(frames.begin(), frames.end(), cmp);
                int popedNum = frames.back().num;
                recommendationCounts[popedNum] = 0; // 삭제됐으니 추천수 0
                isInFrames[popedNum] = false;
                frames.pop_back(); // 빼버리기
 
                frames.push_back({ num,i });
                isInFrames[num] = true;
            }
            else // 여유있을경우
            {
                frames.push_back({ num,i });
                isInFrames[num] = true;
            }
        }
    }
 
    sort(frames.begin(), frames.end(), cmp1);
    
    for (int i = 0; i < frames.size(); ++i)
    {
        printf("%d ", frames[i].num);
    }
 
    return 0;
}
 
 

 

인풋값이 적어서 필요할때마다 sort 해준다 생각하면 쉽게 풀 수 있는 문제.

추천수를 따로 들고있어서 필요에따라 ++해주거나 0으로 초기화시켜줘야 한다.

현재 사진틀에 들어있는지 아닌지에 대한 여부도 따로 들고있어야 한다.

 

현재 추천받은 학생이 사진틀에 없을경우, 두 경우로 나뉜다.

 

1. 사진틀에 더 넣을 수 있는 경우

2. 사진틀에 더 넣을 수 없는경우(꽉차있는경우)

 

사진틀에 더 넣을수있으면 현재 학생번호와 넣은 시간대를 그대로 사진틀에 노드화시켜서 넣으면 된다.

넣었으니 넣었다는 표시를 해준다.

 

사진틀에 더 넣을수 없는 경우, 문제의 조건에 맞는 학생의사진을 틀에서 빼내야 한다.

조건에 맞게 비교함수 cmp를 작성해줘야 한다. 조건에 맞는 학생이 맨 뒤에오게 해주면 된다.

그래야 O(1)로 제거할 수 있기 때문.

조건에 맞는 학생을 꺼내서 해당 학생의 추천수를 0으로, 프레임안에 들어있는지에 대한 여부를 false로 해주고 현재 학생에 대한 정보를 넣어주면 된다.

 

모든 과정을 마치고 학생번호를 오름차순으로 출력해주면 끝.