알고리즘[Greedy]_백준_1931

[문제 분석]

회의시간이 겹치지 않도록 최대한 많은 회의가 진행되어야 합니다. 그렇다면 어떤 회의를 먼저 진행시켜야 할까요? 시작시간이 빠른 회의를 먼저 배치하게 된다면, 회의시간이 얼마나 걸리는지까지 고려해야 하기 때문에, 종료시간을 기준으로 종료시간이 빠를수록 다음 회의를 배치하고 최대한 많은 회의를 진행할 수 있습니다. 

주어진 예제 입력값에는 종료시간이 겹치는 경우가 없지만, 문제를 풀기 위해서는 겹치는 경우도 생각해 보아야 합니다. 예를 들어 (2 2), (1 2)이렇게 두 가지의 회의가 있다고 했을 때, 시작시간이 1인 것을 먼저 배치하면, 해당 회의가 끝나자마자 (2 2)회의를 진행할 수 있습니다. 하지만 (2 2)를 먼저 진행하게 되면 회의가 진행되는 시간이 겹치기 때문에 그 뒤에는 (1 2)회의를 배치할 수 없습니다. 즉, 종료시간이 빠른 것을 기준으로 회의를 정렬할텐데, 종료시간이 같은 경우에는 시작시간이 빠른 것을 먼저 배치하도록 하겠습니다. 

[조건]

1. 종료시간이 빠른 순서로 정렬  
2. 종료시간이 같다면 시작시간이 빠른 순서로 정렬

문제를 풀기 전에 시간값을 기준으로 회의를 위의 조건에 맞도록 직접 배치해보면서 직접 입력 값을 분석해보겠습니다. 

주어진 예제입력을 눈으로 보기 편하게 도식화하면 다음과 같습니다.

다음으로 조건을 성립하도록 회의를 겹치치 않게 최대한 많이 배치하게 되면 다음과 같습니다.

회의1, 회의4, 회의8, 회의 11에게 회의실을 할당해주면서 총 4번의 회의를 진행하도록 할 수 있습니다. 

그럼 이를 토대로 구조를 작성해보자면, 

• N(회의 개수) A(회의 정보 저장[시작시간 종료시간])
• 기준에 맞도록 A객체 혹은 배열을 정렬
• for(회의 개수 만큼 반복)
•     if(이전 회의 종료시간 <= 새로운 회의 시작시간)
•         현재 진행중인 회의 종료시간을 변수에 저장시켜 기억하기 
•         진행할 수 있는 회의의 수를 계산하는 변수 1증가 시키기
• 총 진행 가능 회의 수 진행하기

마지막으로 실제 코드를 작성해보겠습니다.

[방법 1] 2차원 배열 사용

package Greedy;
 
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.Comparator;
import java.util.StringTokenizer;
 
 
public class _1931_v2 {
 
    public static void main(String[] args) throws IOException{
        // TODO Auto-generated method stub
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st;
        
        //전체 회의의 개수
        int N = Integer.parseInt(br.readLine());
        //2차원 배열
        int a[][] = new int[N][2];
        
        //데이터 셋
        for(int i=0; i<N; i++) {
            st = new StringTokenizer(br.readLine()," ");
            int start_time = Integer.parseInt(st.nextToken());
            int end_time = Integer.parseInt(st.nextToken());
            //각 행의 0열 시작 시간
            a[i][0] = start_time;
            //각 행의 1열 종료 시간
            a[i][1] = end_time;
        }
        //정렬
        Arrays.sort(a, new Comparator<int []>() {
            //2차원 배열을 1차원배열의 타입으로 저장했으니, 매개변수 o1과 o2는 각 행의 대한 1차원 배열을 나타낸다. 
            //ㄴ> 2차원 배열의 각 행을 자료형으로 넘기는 것이다.
            @Override
            public int compare(int[] o1, int[] o2) {
                // TODO Auto-generated method stub
                if(o1[1] == o2[1]) {
                    return o1[0] - o2[0];
                }else {
                    return o1[1] - o2[1];
                }
            }
        });
        
        //배치할 수 있는 전체 회의의 수
        int count = 0;
        //전체적인 흐름의 종료시간
        int end = 0;
        
        for(int i=0; i<N ; i++) {
            //처음은 현재 시점에서 가장 먼저 시작하는 회의를 찾고
            //두 번째부터는 갱신된 이전회의의 종료시간보다 큰 시작시간을 찾는다.
            if(a[i][0] >= end) {
                count++;
                end = a[i][1];
            }
        }
        System.out.println(count);
    }
 
}
 

 

[방법2] 객체배열 사용

package Greedy;
 
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.Comparator;
import java.util.StringTokenizer;
 
class A {
    int start_time = 0;
    int end_time = 0;
    
    
    public A(int start_time, int end_time) {
        // TODO Auto-generated constructor stub
        this.start_time = start_time;
        this.end_time = end_time;
    }
}
 
public class _1931 {
 
    public static void main(String[] args) throws IOException{
        // TODO Auto-generated method stub
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st;
        
        //전체 회의의 개수
        int N = Integer.parseInt(br.readLine());
        //객체 배열
        A a[] = new A[N];
        
        //데이터 셋
        for(int i=0; i<N; i++) {
            st = new StringTokenizer(br.readLine()," ");
            int start_time = Integer.parseInt(st.nextToken());
            int end_time = Integer.parseInt(st.nextToken());
            a[i] = new A(start_time, end_time);
        }
        //정렬
        Arrays.sort(a, new Comparator<A>() {
            public int compare(A a1, A a2) {
                if(a1.end_time == a2.end_time) {
                    return a1.start_time - a2.start_time;
                }else {
                    return a1.end_time - a2.end_time;
                }
                
            }
        });
        //배치할 수 있는 전체 회의의 수
        int count = 0;
        //전체적인 흐름의 종료시간
        int end = 0;
        
        for(int i=0; i<N ; i++) {
            //처음은 현재 시점에서 가장 먼저 시작하는 회의를 찾고
            //두 번째부터는 갱신된 이전회의의 종료시간보다 큰 시작시간을 찾는다.
            if(a[i].start_time >= end) {
                count++;
                end = a[i].end_time;
            }
        }
        System.out.println(count);
    }
 
}
 

 

문제 출처 : https://www.acmicpc.net/problem/1931