Greedy(그리디) - 백준 11000 - 강의실 배정 - JAVA : 그리디 무조건 푸는 공식!!!!!

이제 알고리즘을 꾸준히 풀어야겠다....

일단 그리디라는 것은 가장 중요하게 생각할 것은 현재 최적의 해를 구하는거지

그러면 그리디고 뭐고 일단은 최적의 해를 구할 아이디어를 낼줄 아냐 모르냐인거다.

강의실을 가장 적게 쓰기 위해서는 강의실 시간표에 강의를 꽉꽉 채워넣어야 한다.

!!!!그리디 무조건 푸는 공식!!!!

현재 상황에서 최적의 해를 구하자

두가지 키워드가 중요하다. 현재 상황과 최적의 해

현재 상황

강의실 시간표에 수업을 적어 넣을꺼다

-> 보통 현재 상황을 가정하면 거기에서 나온 키워드를 순회하면서 최적의 해를 구하게 된다.
-> 우리가 입력으로 받은건 수업

-> 수업 리스트를 반복하면서 어떻게 하면 최적해를 구해낼지 고민을 하면 된다.

최적의 해

최적해를 구하는건 순전히 아이디어 싸움이다. 그리디랑 관련이 없다. 이것을 생각해내지 못한다면 걍 그 문제는 못푸는 것

이 문제에서의 최적해를 구하는 아이디어는 수업들 중에서 가장 빨리 시작하면서 가장 빨리 끝나는 애를 집는 것이 최적해이다.

가장 빨리 시작하면서 빨리 끝나는 수업을 강의실 시간표에 넣어놓고(이부분도 코드상에서 어떻게 구현이 되어야할지 고민하는 것도 포인트) 수업을 순회하면서 그다음에 가장 빨리 시작하면서 가장 빨리끝나는애를 시간표에 넣어놓고... 이런식으로 구현을 하면 된다.

 

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Collection;
import java.util.Collections;
import java.util.List;
import java.util.PriorityQueue;
import java.util.Queue;
import java.util.StringTokenizer;

public class Main {
    public static void main(String[] args) throws IOException {
        new Main().solution11000();
    }

    class Class implements Comparable<Class> {
        int startTime;
        int endTime;

        public Class(int startTime, int endTime) {
            this.startTime = startTime;
            this.endTime = endTime;
        }

        @Override
        public int compareTo(Class o) {
            if (this.startTime == o.startTime) {
                return this.endTime - o.endTime;
            }
            return this.startTime - o.startTime;
        }
    }

    public void solution11000() throws IOException {
        BufferedReader bufferedReader = new BufferedReader(new InputStreamReader(System.in));
        int n = Integer.parseInt(bufferedReader.readLine());
        StringTokenizer stringTokenizer;
        List<Class> classList = new ArrayList<>();
        for (int i = 0; i < n; i++) {
            stringTokenizer = new StringTokenizer(bufferedReader.readLine());
            int startTime = Integer.parseInt(stringTokenizer.nextToken());
            int endTime = Integer.parseInt(stringTokenizer.nextToken());
            classList.add(new Class(startTime, endTime));
        }
        Collections.sort(classList);
        Queue<Integer> classRoomTable = new PriorityQueue<>();
        for (Class aClass : classList) {
            if (classRoomTable.peek() != null && classRoomTable.peek() <= aClass.startTime) {
                classRoomTable.poll();
            }
            classRoomTable.add(aClass.endTime);
        }
        System.out.println(classRoomTable.size());
    }
}

 

정리

1. 현재 상황이 무엇인지 정의를 내려본다.
-> 수업을 가지고 강의 시간표를 채워넣는다.

2. 현재 상황에서 내가 어떤 키워드를 순회할 수 있을지 생각해본다.

-> 수업이라는 키워드, 나는 수업 리스트를 입력 받았다.

3. 최적의 해를 구하는 방법을 생각해본다.

-> 가장 빨리 시작하고 가장 빨리 끝나는 수업을 찾아서 앞에 수업이랑 겹치는지를 확인하면서 시간표를 채우는 것이 방법

4. 최적의 해를 위해서 순회할 자료구조를 어떻게 정렬할 수 있을지 고민해본다.

-> class 라는 클래스를 만들어서 compareTo를 구현하여 내가 원하는 방식대로 정렬을 해준다.

5. 자료구조를 순회하면서 최적의 해를 구하는 방법을 생각했으면 문제에서 원하는 답을 어떤 방식으로 저장해야할지 고민한다.

-> Queue에 끝나는 시간을 저장해서 자료구조에서 꺼낸 수업의 시작시간이 앞서 끝난 시간과 같거나 그 뒤면 Queue에 새로운 끝나는 시간을 저장해주고 없으면 새로 Queue에 값을 넣는다.
-> 이렇게 되면  Queue의 Size가 강의실의 개수