(Baekjoon) GreedyAlgorithm - (3) 회의실배정

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

1931번: 회의실배정

 

 

끝나는시간을 오름차순으로 정리 >> 시작시간 오름차순정리

 

그리고 끝나는시간보다 큰 시작시간인 회의로 넘어가고

그다음에도 끝나는시간보다 큰 시작시간인 회의로 넘어간다.

 

왜 이런식으로 가는지는 GreedyAlgorithm은 일단은 빠른것부터 선택하는것이 중점인데 

이러한 Algorithm이 적용되는 몇몇예중에 하나가 회의시간 결정이다.

구글링중에 동적프로그래밍이 쓸데없이 많이 연산하는것을 낭비하기위해 최적화하기 위해 

GreedyAlgorithm이 쓰인다고 하는데 많이 경험해보면 알것이다.

 

그리디알고리즘의 핵심은 결론적으로 멍청할 결정이더라도 일단은 빠른길부터 선택하는것이다.

(마시멜로는 기다리는것보다 1개있을때 먹는게 좋다라는 알고리즘이라 생각하면 된다.)

 

Arrays.sort는 오름차순으로 정렬을 하기위함이다.

Arrays.sort의 자세한 사용방법은

https://sudeky.tistory.com/76

(basic) 입/출력, 배열, JVM, Buffer 등..

Ctrl+F 로 Arrays.sort목록에서 찾아보면된다.

 

package GreedyAlgorithm;

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

public class _1931 {
    public static void main(String[] args) {
        try{
            BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
            int conf = Integer.parseInt(br.readLine());
            int conf_time[][] = new int[conf][2];
            for (int i = 0; i < conf; i++){
                StringTokenizer st = new StringTokenizer(br.readLine());
                conf_time[i][0] = Integer.parseInt(st.nextToken());
                conf_time[i][1] = Integer.parseInt(st.nextToken());
            }
            
            Arrays.sort(conf_time, new Comparator<int[]>() {

                @Override
                public int compare(int[] o1, int[] o2) {
                    if(o2[1]==o1[1]) {
                        return o1[0]-o2[0];
                    }
                    return  o1[1] - o2[1];
                }
            });

            int i = 0;
            int j = 0;
            int count=1;
            while(i < conf_time.length){
                if(conf_time[j][1] <= conf_time[i][0]){
                    count++;
                    j = i;
                }
                i++;
            }
            System.out.println(count);
            
            


        } catch (IOException e){
            e.printStackTrace();
        }


    }
}

 

 

 

 

 

 

 

백준문제풀이Github : 

https://github.com/sdk0213/baekjoon-study

sdk0213/baekjoon-study