BOJ 14572 스터디 그룹

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

문제

신입생 현우는 알고리즘 공부가 정말 재밌다.

현우는 이번에 스터디 그룹을 만들어 더욱 열심히 공부해보려 한다.

하지만 사공이 많으면 배가 산으로 간다고, 그룹에 참여하는 학생이 너무 많을 경우 지지부진한 결과가 나오게 될 것을 우려한 현우는 아래와 같은 조건을 내걸었다.

그룹 내에서 가장 잘 하는 학생과 가장 못 하는 학생의 실력 차이가 D 이하여야 한다.

또한, 그룹의 효율성 E를 아래와 같이 정의하였다.

E = (그룹 내의 학생들이 아는 모든 알고리즘의 수 - 그룹 내의 모든 학생들이 아는 알고리즘의 수) * 그룹원의 수

현우는 위와 같은 두 가지 조건을 체크하기 위해, 모든 학생들의 실력을 수치화하고, 중요한 알고리즘 K개에 대해, 각 학생들이 어떤 알고리즘을 알고 있는지를 모두 조사하였다.

현우는 조건을 만족하는 학생들의 부분집합 중 효율성이 최대가 되는 그룹을 뽑아 스터디 그룹으로 만들 생각이다.

현우가 만들 스터디 그룹의 효율성은 얼마가 될까?

---

입력

첫 줄에 학생의 수 N, 알고리즘의 수 K, 문제에 설명한 D가 주어진다. $(1 ≤ N ≤ 10^5, 1 ≤ K ≤ 30, 0 ≤ D ≤ 10^9)$

이어 N명의 학생에 대한 정보가 아래와 같이 주어진다.

• $M d (0 ≤ M ≤ K, 0 ≤ d ≤ 10^9)$: 해당 학생이 알고 있는 알고리즘의 수, 해당 학생의 실력
• 다음 줄에, M개의 정수 $A_i$: 해당 학생이 알고 있는 알고리즘들 $(1 ≤ A_i ≤ K)$

---

출력

가장 효율성이 높은 그룹의 효율성을 출력한다.

---

예제 입력 1

3 3 10
1 20
1
1 10
2
1 0
3

예제 출력 1

4

---

코드

이번 문제는 학생의 실력을 기준으로 오름차순으로 정렬 후 투포인터를 사용하여 해결하는 문제였다.

알고리즘 종류의 수(K)가 30이하이므로 각 학생이 알고있는 알고리즘을 배열이 아닌 비트마스크로 표현해 메모리를 아낄 수 있었다.

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.StringTokenizer;

public class Main {

    static class Student implements Comparable<Student> {
        int algorithm; // 학생이 알고있는 알고리즘을 비트마스크로 표현
        int d; // 학생의 실력

        public Student(int algorithm, int d) {
            this.algorithm = algorithm;
            this.d = d;
        }

        @Override
        public int compareTo(Student o) {
            return d - o.d;
        }
    }

    static Student[] students;
    static int[] algorithms;
    static int N, K, D;

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        N = Integer.parseInt(st.nextToken());
        K = Integer.parseInt(st.nextToken());
        D = Integer.parseInt(st.nextToken());
        algorithms = new int[K];
        students = new Student[N];
        for (int i = 0; i < N; i++) {
            st = new StringTokenizer(br.readLine());
            int size = Integer.parseInt(st.nextToken()), d = Integer.parseInt(st.nextToken()), algorithm = 0;
            st = new StringTokenizer(br.readLine());
            for (int j = 0; j < size; j++) {
                int algo = Integer.parseInt(st.nextToken());
                algorithm |= 1 << algo - 1;
            }
            students[i] = new Student(algorithm, d);
        }
        Arrays.sort(students); // 입력받은 학생들을 실력을 기준으로 오름차순 정렬

        // maxE는 계산된 최고 효율성, lIdx는 왼쪽 포인터, rIdx는 오른쪽 포인터를 의미
        int maxE = Integer.MIN_VALUE, lIdx = 0, rIdx = 0;

        /**
         * 가장 잘하는 학생과 가장 못하는 학생의 실력 차이가 D보다 크면, 왼쪽 포인터를 +1 하고
         * D 이하일 경우, 오른쪽 포인터를 +1 하며 두 포인터 사이에 있는 학생들의 효율성을 계산
         */
        while (rIdx < N) {
            int gap = students[rIdx].d - students[lIdx].d;
            if (gap <= D) {
                for (int i = 0; i < K; i++)
                    if ((students[rIdx].algorithm & 1 << i) != 0) algorithms[i]++;

                maxE = Integer.max(maxE, calE(lIdx, rIdx));
                rIdx++;
            } else {
                for (int i = 0; i < K; i++)
                    if ((students[lIdx].algorithm & 1 << i) != 0) algorithms[i]--;
                lIdx++;
            }
        }

        System.out.println(maxE);
    }

    // 효율성을 계산하는 메소드
    static int calE(int lIdx, int rIdx) {
        int whole = 0, allKnown = 0, numOfStudents = rIdx - lIdx + 1;

        for (int i = 0; i < K; i++) {
            if(algorithms[i] == numOfStudents) {
                whole++;
                allKnown++;
            } else if (algorithms[i] > 0) whole++;
        }

        return (whole - allKnown) * numOfStudents;
    }
}