[백준]1931번 : 회의실 배정- JAVA[자바]

1931번 : 회의실 배정-

---

문제해결을 돕기 위한 그림

방법1. Scanner-(Class 객체와 Comparable를 Implement하기)

import java.util.ArrayList;
import java.util.Collections;
import java.util.Scanner;
// 입력받을 회의 시작시간, 회의 끝시간을 Time클래스로 받는다.
class Time implements Comparable<Time> {
					// 두개의 값으로 이루어진 값을 비교하기 위해서
  					// Comparable을 Implemnet받고 <Time>클래스에서 비교한다.
  	// 시작시간을 받을 변수
  	int start;
  	// 끝시간을 받을 변수
	int end;
	// 시작시간과 끝시간을 받는 생성자
	Time(int start, int end) {
		this.start = start;
		this.end = end;
	}
	// 아래에서 Time 객체를 비교하기 위한 오버라이딩
  	// compareTo를 재정의하여 아래에서 List에 담긴 
  	// Time클래스를 오름차순으로 정렬 할 수 있다.
    @Override
    public int compareTo(Time t) {
  		// end = 회의 끝나는 시간이 클수록 더 큰값
        if (this.end > t.end) { // 끝나는 시간 기준 오름차순 정렬 
            return 1;
  		// 회의 끝나는 시간이 같다면
        } else if (this.end == t.end) {
            if(this.start > t.start) { // 끝나는 시간 같다면 시작 시간 기준 오름차순 
            	return 1;
            // 희의 끝나는 시간이 같고 this.start < t.start 인경우
  			} else {
               // this가 더 작아지므로 -1로 return
            	return -1;
            }
        // this.end < t.end인 경우        
        } else {
  		// this가 더 작아지므로 -1로 return
        	return -1;
        }
    }
  	// compareTo를 이런식으로 재정의 했으므로 
  	// 문제 해결의 돕기 위한 그림과 같이 정렬된다.
}

public class Main {

	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
  		// 회의의 수를 받음
		int N = sc.nextInt();
		// a b 로 입력 받을 값을 Time 객체로 받아 List에 담는다.
		ArrayList<Time> timeList = new ArrayList<>();
		for(int i = 0; i < N; i++) {
           	// 입력 받은 수를 a, b에 담는다.
			int a = sc.nextInt();
			int b = sc.nextInt();
			// a, b를 Class Time 객체에 담아 timeList에 담아준다.
			timeList.add(new Time(a, b));
		}
		// timeList를 오름차순으로 정렬한다. 
  		// Comparable을 통해 재정의 했기 때문에 가능
  		// 만약, 재정의를 안했다면, Time객체는 2개의 값을 가지므로
  		// 오름차순 정렬할 때 예외가 발생함
		Collections.sort(timeList);
		// 회의 수. 기본적으로 최소 1개부터 시작
		int ans = 1;
  		// 정렬된 timeList안의 Time 객체들 이므로
  		// 0번 째 방의 end는 회의 시작하는 시간이 가장 작고
  		// 회의 끝나는 시간도 가장 작다.
		int endTime = timeList.get(0).end;
		for(int i = 1; i < timeList.size(); i++) {
            // timeList의 0번째 방의 회의 끝나는 시간보다 크거나 같으면서
            // 가정 먼저 시작되는 timeList의 i번 째 방을 찾는다.
			if(timeList.get(i).start >= endTime) {
  				// 그렇게 찾은 i번째 방은 timeList의 0번째 방의 
  				// 회의 끝나는 시간보다 회의 시작시간이 크거나 같고
  				// 회의 끝나는 시간이 가장 작다
				endTime = timeList.get(i).end;
  				// if문제 들어오는 timeList의 i번째 방을 찾을 때마다
  				// ans를 1 증가 시킨다.
				ans++;
			}
		}
		// 가장 많이 회의 할 수 있는 값 출력
		System.out.println(ans);
	}
}

방법2 Scanner-Comparator사용

import java.util.Scanner;
import java.util.Arrays;
import java.util.Comparator;

public class Main {

	public static void main(String[] args) {

		Scanner in = new Scanner(System.in);
		
		int N = in.nextInt();
		
		
		/*
		  time[][0] 은 시작시점을 의미 
		  time[][1] 은 종료시점을 의미 
		*/
		int[][] time = new int[N][2];
		
		
		for(int i = 0; i < N; i++) {
			time[i][0] = in.nextInt();	// 시작시간 
			time[i][1] = in.nextInt();	// 종료시간 
		}
		
		
		// 끝나는 시간을 기준으로 정렬하기 위해 compare 재정의 
		Arrays.sort(time, new Comparator<int[]>() {
		//time이란 변수를 이렇게 정렬하겠다는 문법임
			@Override
			public int compare(int[] o1, int[] o2) {
				
				// 종료시간이 같을 경우 시작시간이 빠른순으로 정렬해야한다.  
				if(o1[1] == o2[1]) {// 
					return o1[0] - o2[0];
				}
				// 종료시간을 오름 차순으로 정렬
				return o1[1] - o2[1];
			}

		});
		
		int count = 0;
		int prev_end_time = 0;
		
		for(int i = 0; i < N; i++) {
			
			// 직전 종료시간이 다음 회의 시작 시간보다 작거나 같다면 갱신 
			if(prev_end_time <= time[i][0]) {
				prev_end_time = time[i][1];
				count++;
			}
		}
		
		System.out.println(count);
	}

}

참고자료

Class 객체와 Comparable을 코드 알고리즘

https://minhamina.tistory.com/119

Comparator 활용한 방법

https://st-lab.tistory.com/145

Comparable, Comparator를 이용한 ArrayList 정렬

https://includestdio.tistory.com/35

2차원 배열 Comparator 방법

https://seeminglyjs.tistory.com/164