[Algorithm]Baekjoon 2461번 :: 대표 선수

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

 

 

#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>
#include <unordered_set>
 
using namespace std;
 
struct Node
{
    int classNum;
    int ability;
};
 
bool cmp(const Node& a, const Node& b)
{
    return a.ability < b.ability;
}
 
int n, m, num;
vector<Node> students;
unordered_map<int, int> check;
 
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
 
    cin >> n >> m;
 
    for (int i = 0; i < n; ++i)
    {
        for (int j = 0; j < m; ++j)
        {
            cin >> num;
            students.push_back({ i,num });
        }
    }
 
    sort(students.begin(), students.end(), cmp);
    // 윈도우사이즈는 n. n개만큼 유지되어있어야함.
 
    int answer = 0x3f3f3f3f;
    int count = 0;
    int start = 0;
    int end = 0;
 
    while (end < students.size())
    {
        auto iter = check.find(students[end].classNum);
        
        if (iter == check.end()) // 현재 구간에 없으면
        {
            check.insert({ students[end].classNum, 1 });
        }
        else // 있으면
        {
            ++iter->second;
        }
 
        while (check.size() == n)
        {
            answer = min(answer, students[end].ability - students[start].ability);
 
            auto iter = check.find(students[start].classNum);
 
            if (iter->second > 1)
            {
                --iter->second;
            }
            else
            {
                check.erase(iter);
            }
 
            ++start;
        }
 
        ++end;
    }
 
    cout << answer;
}
 
 

 

이전 눈사람문제를 풀었었어서 접근은 정확하게 했다.

다만, 배열로 체크하는게 아직 헷갈리다보니까 오히려 꼬여서, map으로 먼저 풀고 그다음에 배열로 체크해서 시간을 줄이던가 해야할 것 같다.