백준 1931번 - 회의실 배정(자바)

문제 설명

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

​

입력

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

​

출력

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

​

예제 입력 1

11 1 4 3 5 0 6 5 7 3 8 5 9 6 10 8 11 8 12 2 13 12 14

예제 출력 1

4

힌트

(1,4), (5,7), (8,11), (12,14) 를 이용할 수 있다.

문제 풀이

먼저 이 문제를 보고 생각이 들었던 것은 회의시간이 끝나는 순서대로 맞추어 정렬을 한 후 초기값은 맨 앞의 값으로 하고 뒤로 가면서 초기 회의시간의 끝나는 시간보다 크거나 같으면 해당 회의를 진행하도록 하는 식으로 가닥을 잡았다.

입력으로 예를 들어보자면,

(1 , 4) (3, 5) (0, 6) (5, 7) (3, 8) (5, 9) (6, 10) (8, 11) (8, 12) (2, 13) (12, 14)

이렇게 끝나는 시간 순으로 정렬을 하고 맨 앞의 값인( 1,4 )를 초기값으로 잡는다.

그 다음 4보다 크거나 같아야 회의가 시작할 수 있으므로 2번째 3번째 회의는 진행될 수 없고 (5,7)인 4번째 회의가 진행된다. 이렇게 되면 5,7의 회의가 끝나는 시간인 7보다 크거나 같은 회의 중 더 회의시간이 빨리 끝나는 (8,11)을 그다음으로 잡고 11보다 크거나 같은 (12,14)회의가 진행되며 총 4번의 회의가 진행된다.

그래서 나는 하기와 같이 코드를 구성했고 , 나는 처음에는 맨 끝의 값을 기준으로만 오름차순을 했는데.. 백준에 제출해보니 틀려서 뭐가 문제지 고민하다가 구글링을 했다.

해보니 회의 종료시간이 같을 때는 회의 시작 시간 순으로 정렬해야한다는 것을 알았다.

근데 어차피.. 개수 세는 건데 저게 중요한 가 싶은데 잘 모르겠다.

혹시 아시는 분이 있으면 댓글 달아주시면 감사하겠습니당

package Programmers.Backjun20221213;

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

public class exam1 {
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st = new StringTokenizer(br.readLine());
int[][] conference = new int[Integer.parseInt(st.nextToken())][2];
for (int i = 0; i < conference.length; i++) {
st = new StringTokenizer(br.readLine());
conference[i][0] = Integer.parseInt(st.nextToken());
conference[i][1] = Integer.parseInt(st.nextToken());
}

    Arrays.sort(conference,(x,y) -> {
        //요 부분이 제가 의문을 가지는 부분입니다. 굳이 필요한가요?
        if(x[1] == y[1]){
            return x[0] - y[0];
        }
        ////////////////////////////////////////////////////////
        return x[1]-y[1];
    });

    int cnt = 1;
    int finishTime = conference[0][1];
    for (int j = 1; j < conference.length; j++) {
        if(finishTime > conference[j][0]){
            continue;
        }
        cnt++;
        finishTime = conference[j][1];
    }
    System.out.println(cnt);
}

}