[코딩테스트] 백준(BAEKJOON) - 회의실 배정(Java, 1931번)

안녕하세요~

 

이번에 풀어볼 문제는 회의실 배정! 이라는 문제입니다.

 

문제의 알고리즘은 간단했으나

아무래도 쌍 즉 값이 두 개가 있어서 이부분에 대한 처리를 어떻게 하나 고민을 좀 했네요.

 

또한 sort도... override를 사용해보지 않다보니 어려웠습니다.

문제 만나보시죠!

 

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

1931번: 회의실 배정

 

대표적인 그리드 문제죠~

코드 보여드리고다음에 제가 푼거 설명~드리겠습니다.

 

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collections;
import java.util.Comparator;
import java.util.List;
import java.util.PriorityQueue;
import java.util.Scanner;
import java.util.StringTokenizer;


public class Main {
		public static void main(String[] args) throws NumberFormatException, IOException {
			BufferedReader bf=new BufferedReader(new InputStreamReader(System.in));
			
			int count=Integer.parseInt(bf.readLine());
			int [][] arr=new int[count][2];
			
			
			String line="";
			
			for(int i=0;i<count;i++)
			{
				line=bf.readLine();
				
				arr[i][0]=Integer.parseInt(line.split(" ")[0]);
				arr[i][1]=Integer.parseInt(line.split(" ")[1]);
			}
			
			Arrays.sort(arr, new Comparator<int[]>() {
				@Override
				public int compare(int[] o1, int[]o2)
				{
					if(o1[1]==o2[1])
						return o1[0]-o2[0];
					
					return o1[1]-o2[1];
				}

			});
			
			int answer=0;
			int endTime=0;
			
			for(int i=0;i<count;i++)
			{
				if(endTime<=arr[i][0])
				{
					answer++;
					endTime=arr[i][1];
				}
			}
			
			System.out.println(answer);

			
	}

}

네~ 게으름뱅이인 저답게 코드가 아주 지저분 합니다.

그러나 핵심 부분만 간단하게 짚고 넘어가겠습니다.

 

우리가 주목해야될 건 한 번에 입력받는 쌍 중 두번째 값입니다.

 

앞의 값이 어떻든간에~ 일단 두 번째 값들이 작아야 많이 넣을 수 있겠죠?

4 11보다는 4,6,8,10,11과 같이 회의실 배정이 더 많듯이 말이죠~

 

①입력받은 pair 저장

②pair의 2번째 값끼리 오름차순으로 sort!

③여기서 sorting할때 주의할 점! 두 번째값이 같다면 첫번째 값이 작은게 우선순위를 부여합니다.

(1,1) (2,3) (3,4), (4,4)가 있다고한다면 (1,1) (2,3) (4,4), (3,4) 이렇게 정렬되면 (3,4)하나를 놓치게 되기 때문이죠~

④이제는 오름차순으로 정렬된 pair를 하나씩 뽑는다. 다만! n번째 순서의 쌍을 뽑을때 회의실이 배정되려면

n-1번째의[1]보다 n번째의[0]의 값이 크거나 같아야합니다.

그래야 회의시간이 겹치지 않겠죠~?

 

네~ 이렇게 풀어주시면 해결되겠습니다.

 

감사합니다. :D