[자바] 백준 14572 - 스터디 그룹 (java)

 문제 : boj14572

---

 

필요 알고리즘 개념

• 그리디
  
  • 풀이를 보면 왜 그리디인지 알 수 있다!
• 투 포인터 (두 포인터)
  
  • 이 문제의 경우 그리디 규칙을 적용시킬 때 투 포인터로 적용하는게 편하다.

※ 제 코드에서 왜 main 함수에 로직을 직접 작성하지 않았는지, 왜 Scanner를 쓰지 않고 BufferedReader를 사용했는지 등에 대해서는 '자바로 백준 풀 때의 팁 및 주의점' 글을 참고해주세요. 백준을 자바로 풀어보려고 시작하시는 분이나, 백준에서 자바로 풀 때의 팁을 원하시는 분들도 보시는걸 추천드립니다.

 

---

 

풀이

  효율성 E를 구할 때 필요한 요소들을 하나씩 살펴보자.

1. 그룹 내의 학생들이 아는 모든 알고리즘의 수

-> 학생 수가 늘어나면 항상 동일하거나 늘어난다.

2. 그룹 내의 모든 학생들이 아는 알고리즘의 수

-> 학생 수가 늘어나면 항상 동일하거나 감소한다.

3. 그룹원의 수

-> 학생 수가 늘어나면 항상 증가한다.

 

  E를 최대치로 만들려면 '1'은 증가해야하고, '2'는 감소해야하고, '3'은 증가해야 한다. 그럼 전부 학생 수가 늘어나면 그렇게 된다는걸 알 수 있다!

 

  즉, 그냥 최대한의 학생을 그룹에 포함시킬수록 무조건 이득이다(그리디).

그렇다면 미리 학생의 실력 d를 기준으로 정렬을 해둔다면,

임의의 s, t에 대해 [s, t] 그룹 내 가장 잘하는 학생과 가장 못하는 학생의 실력차이는 t학생의 실력 - s학생의 실력이 될 것이다. 즉 [s, t]에 대해 t의 실력-s의 실력이 D 이하이면서, 학생수가 최대치인 그룹들에 대해 E를 구하고 그 중 최대치를 출력해주면 된다.

 

  [s, t] 에서 s, t를 어떻게 구성할지가 이제 문제인데, 투 포인터를 사용하면 어렵지 않게 진행할 수 있다.

투 포인터 로직은 다음과 같이 정하면 된다.

 

A. gap = t의 실력 - s의 실력

B. gap이 D 초과이라면 현재 s 학생이 알고있는 알고리즘들을 E를 계산할 때 필요한 요소에서 제외하고, s를 증가한다.

C. gap이 D 이하라면 E를 계산해서 E의 최대치를 갱신한 후, t를 증가시킨다. 그리고 증가된 t에 해당하는 학생이 알고있는 알고리즘을 E의 요소들을 계산할 수 있도록 추가한다.

 

 

---

 

코드 : github

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

class Student implements Comparable<Student> {
    int power;
    ArrayList<Integer> algo;
    public Student(int power, ArrayList<Integer> algo) {
        this.power = power;
        this.algo = algo;
    }

    @Override
    public int compareTo(Student o) {
        return this.power - o.power;
    }
}
public class Main {
    private int getE(int[] arr, int s, int e) {
        int cnt1 = 0;
        int cnt2 = 0;
        int n = e-s+1;
        for (int i = 0; i < arr.length; i++) {
            if (arr[i] != 0) cnt1++;
            if (arr[i] == n) cnt2++;
        }
        return (cnt1-cnt2)*n;
    }
    private void solution() throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        int n = Integer.parseInt(st.nextToken());
        int k = Integer.parseInt(st.nextToken());
        int d = Integer.parseInt(st.nextToken());
        Student[] students = new Student[n];
        for (int i = 0; i < n; i++) {
            st = new StringTokenizer(br.readLine());
            int m = Integer.parseInt(st.nextToken());
            int power = Integer.parseInt(st.nextToken());
            ArrayList<Integer> algo = new ArrayList<>(m);
            st = new StringTokenizer(br.readLine());
            while (m-->0) algo.add(Integer.parseInt(st.nextToken()));
            students[i] = new Student(power, algo);
        }
        Arrays.sort(students);

        int[] arr = new int[k+1];
        int max = 0;
        int s = 0;
        int e = 0;
        for (int a : students[0].algo)
            arr[a]++;

        while (true) {
            int gap = students[e].power - students[s].power;
            if (gap <= d) {
                max = Math.max(max, getE(arr, s, e));
                e++;
                if (e >= n)
                    break;

                for (int a : students[e].algo)
                    arr[a]++;
                continue;
            }
            for (int a : students[s].algo)
                arr[a]--;
            s++;
        }
        System.out.println(max);
    }

    public static void main(String[] args) throws Exception {
        new Main().solution();
    }
}