[백준/C++] 14572번: 스터디 그룹

문제 & 링크

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

풀이

1. 각 학생의 정보를 저장하는 벡터를 선언한다. 이때 정렬할 것을 고려하여 학생의 실력을 pair의 first로 두고, 해당 학생이 알고있는 알고리즘들을 벡터로 하여 pair의 second로 둔다.

2. 학생의 정보를 저장해놓은 벡터를 정렬한다.

3. 실력의 차이가 D 이하인 조건을 기준으로 하여 투 포인터 기법을 사용한다. 실력의 차이가 D 이하라면 두 번째 포인터를 한 칸 앞으로 옮기고, 실력의 차이가 D 초과라면 첫 번째 포인터를 한 칸 앞으로 옮긴다.

4. 그룹의 효율성을 구하는 함수를 위해 각 알고리즘을 몇 명이 아는지 저장하는 해쉬맵을 선언한다.

4-1. 그룹 내의 학생들이 아는 모든 알고리즘의 수는 해쉬맵의 value가 1 이상인 key의 개수이다.

4-2. 그룹 내의 모든 학생들이 아는 알고리즘의 수는 해쉬맵의 value가 그룹 인원 수 이상인 key의 개수이다.

1. 벡터의 모든 원소를 투 포인터가 순회하도록 종료 조건을 설정하여 최대 효율성을 구한다.

코드

#include <iostream>
#include <vector>
#include <unordered_map>
#include <algorithm>

using namespace std;

vector<pair<int, vector<int>>> V;

unordered_map<int, int> hash_map;

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    int N, K, D;
    cin >> N >> K >> D;
    

    for (int i = 0; i < N; i++) {
        int M, d;
        cin >> M >> d;
        vector<int> tmp(M);
        for (int j = 0; j < M; j++) {
            cin >> tmp[j];
        }
        V.push_back(make_pair(d, tmp));
    }

    sort(V.begin(), V.end());

    int point1 = 0;
    int point2 = 0;
    for (int i = 0; i < V[point2].second.size(); i++) {
        hash_map[V[point2].second[i]]++;
    }
    int ans = 0;
    int student_cnt = 1;
    while (1) {
        if (point1 == N || point2 == N) break;

        if (V[point2].first - V[point1].first <= D) {
            int all_known_algo_cnt = 0;
            int all_student_known_algo_cnt = 0;

            for (auto& i : hash_map) {
                if (i.second >= student_cnt) all_student_known_algo_cnt++;
                if (i.second >= 1) all_known_algo_cnt++;
            }

            int E = (all_known_algo_cnt - all_student_known_algo_cnt) * student_cnt;
            ans = max(ans, E);

            if (point2 < N - 1) {
                student_cnt++;
                point2++;
                for (int i = 0; i < V[point2].second.size(); i++) {
                    hash_map[V[point2].second[i]]++;
                }
            }
            else {
                for (int i = 0; i < V[point1].second.size(); i++) {
                    hash_map[V[point1].second[i]]--;
                }
                student_cnt--;
                point1++;
            }

        }
        else {
            for (int i = 0; i < V[point1].second.size(); i++) {
                hash_map[V[point1].second[i]]--;
            }
            student_cnt--;
            point1++;
        }
    }
    cout << ans;
}