[그리디 알고리즘 ] 백준 1931 자바

1931.

한 개의 회의실이 있는데 이를 사용하고자 하는 N개의 회의에 대하여 회의실 사용표를 만들려고 한다. 각 회의 I에 대해 시작시간과 끝나는 시간이 주어져 있고, 각 회의가 겹치지 않게 하면서 회의실을 사용할 수 있는 회의의 최대 개수를 찾아보자. 단, 회의는 한번 시작하면 중간에 중단될 수 없으며 한 회의가 끝나는 것과 동시에 다음 회의가 시작될 수 있다. 회의의 시작시간과 끝나는 시간이 같을 수도 있다. 이 경우에는 시작하자마자 끝나는 것으로 생각하면 된다.

 

입력

첫째 줄에 회의의 수 N(1 ≤ N ≤ 100,000)이 주어진다. 둘째 줄부터 N+1 줄까지 각 회의의 정보가 주어지는데 이것은 공백을 사이에 두고 회의의 시작시간과 끝나는 시간이 주어진다. 시작 시간과 끝나는 시간은 231-1보다 작거나 같은 자연수 또는 0이다.

출력

첫째 줄에 최대 사용할 수 있는 회의의 최대 개수를 출력한다.

예제 입력 

11

1 4

3 5

0 6

5 7

3 8

5 9

6 10

8 11

8 12

2 13

12 14

예제 출력 

4

 

해결방법)

 

우선 핵심해결방법은 시작시간에 집중하는게 아니라 회의 종료시간에 우선적으로 집중해야된다

 

즉 배열 한쌍 arr[0][0](0번쨰 회의시작시간) arr[0][1](0번째 회의종료시간)에서  배열 한쌍을 회의 종료시간오름차순으로 정렬시킨후. 종료시간이 같은 회의는 시작시간을 오름차순으로 회의를 정렬한다.

1 2

3 2

3 4

1 5

1 7

2 8

6 8

9 10 이런식으로 정렬이 되었다고 치자

 

1,2 > 3,2는(앞 종료시간이 뒤 시작시간보다 크므로 count x ) > 3,4 (count ) > 1,5 count x > 1,7 count x > 2,8 count x > 6,8 count > 9,10 count

if문으로 시작시간 종료시간 최소 최대값을 잘 설정하여 카운팅해주면 될거같다.

 

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

public class Main {

	public static void main(String[] args) {
		
		Scanner sc = new Scanner(System.in);
		int N = sc.nextInt();
		int temp = 0;
		int demp=0;
		int [][]arr = new int[N][2];
      		
        for (int i = 0; i < N; i++)
        {
            arr[i][0] = sc.nextInt(); //i번쨰 회의시작시간
            arr[i][1] = sc.nextInt(); //i번쨰 회의종료시간
        }
        /* 정렬전
        for(int i=0; i<N; i++) {
        	System.out.printf("arr[%d][%d] : %d   ",i,0,arr[i][0]);
        	System.out.printf("arr[%d][%d] : %d\n",i,1,arr[i][1]);
        }
        */
        
        for(int i=0; i<N; i++) 
        {
        	for(int j=0; j<N-i-1; j++)
        	{
        		if(arr[i][1] > arr[i+1][1])
        		{
        			temp = arr[i][1];
        			arr[i][1] = arr[i+1][1];
        			arr[i+1][1] = temp;
        			
        			demp = arr[i][0];
        			arr[i][0] = arr[i+1][0];
        			arr[i+1][0] = demp;		
        		}  		
        	}       	        	
        }
        /*
        System.out.println("------- 정렬후-----------");
        for(int i=0; i<N; i++) {
        	System.out.printf("arr[%d][%d] : %d ",i,0,arr[i][0]);
        	System.out.printf(" arr[%d][%d] : %d \n",i,1,arr[i][1]);
        }
*/
        
        int count = 0;    // 최대값 변수 
        int end = -1;    // 다음시작 시간과 비교할 변수
        for (int i = 0; i < N; i++) {
            //현재 시작시간이 이전 종료시간보다 늦을 경우 
            if (arr[i][0] >= end) {
                //System.out.println(arr[i][0] + " " + arr[i][1]);
                end = arr[i][1];    //현재 종료시간을 다음 시작시간과 비교하기위해 저장 
                count++;
            }
        }
        System.out.println(count);
	
	
	
}

}

 첫번째 코드는 출력결과값은 맞지만 시간초과가 나서 제출이안된다...

 

package tutorial1;

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

public class Main {

	public static void main(String[] args) {
		
		Scanner sc = new Scanner(System.in);
		int N = sc.nextInt();
		int temp = 0;
		int demp=0;
		int [][]arr = new int[N][2];
      		
        for (int i = 0; i < N; i++)
        {
            arr[i][0] = sc.nextInt(); //i번쨰 회의시작시간
            arr[i][1] = sc.nextInt(); //i번쨰 회의종료시간
        }
        
        for(int i=0; i<N; i++) {
        	System.out.printf("arr[%d][%d] : %d   ",i,0,arr[i][0]);
        	System.out.printf("arr[%d][%d] : %d\n",i,1,arr[i][1]);
        }
        
        
        Arrays.sort(arr, new Comparator<int[]>() {
            @Override
            public int compare(int[] start, int[] end) {
                //start[0], end[0] 배열은 arr[][] 의 첫번째 라인(시작시간)이다.
                //start[1], end[0] 배열은 arr[][] 의 두번째 라인(종료시간)이다.
                if(start[1]==end[1]){
                    //만약 비교하는 값의 종료시간이 같을 경우 시작시간으로 정렬한다.
                    return Integer.compare(start[0], end[0]);
                }
                //종료시간에 따라 정렬한다.
                return Integer.compare(start[1], end[1]);
            }
 
        });
        /*
        System.out.println("------- 정렬후-----------");
        for(int i=0; i<N; i++) {
        	System.out.printf("arr[%d][%d] : %d ",i,0,arr[i][0]);
        	System.out.printf(" arr[%d][%d] : %d \n",i,1,arr[i][1]);
        }
*/
        
        int count = 0;    // 최대값 변수 
        int end = -1;    // 다음시작 시간과 비교할 변수
        for (int i = 0; i < N; i++) {
            //현재 시작시간이 이전 종료시간보다 늦을 경우 
            if (arr[i][0] >= end) {
                //System.out.println(arr[i][0] + " " + arr[i][1]);
                end = arr[i][1];    //현재 종료시간을 다음 시작시간과 비교하기위해 저장 
                count++;
            }
        }
        System.out.println(count);
	
	
	
}

}