백준 1931번 회의실 지정,Java 풀이

백준 1931번 문제 https://www.acmicpc.net/problem/1931

1. 내 방식대로 풀어보기

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        int n = Integer.parseInt(br.readLine());
        int[][] arr = new int[n][2];  // n개의 줄에 각각 2개의 숫자

        // n개의 줄에서 각각 2개의 숫자 입력받기
        for(int i = 0; i < n; i++) {
            String[] input = br.readLine().split(" ");
            arr[i][0] = Integer.parseInt(input[0]);
            arr[i][1] = Integer.parseInt(input[1]);
        }

        // arr[i][0] - arr[i][1] 의 절대값이 작은순서대로 배열을 정렬한다.
        int[][] temp = new int[n][2]; // 회의시간이 짧은 순서대로 버블정렬
        for(int j=0; j<n-1; j++){
            for(int i=0; i<n-1; i++){
                if(Math.abs(arr[i][0] - arr[i][1] ) > Math.abs(arr[i+1][0] - arr[i+1][1] )){
                    temp[i][0] = arr[i][0];
                    temp[i][1] = arr[i][1];
                    arr[i][0] = arr[i+1][0];
                    arr[i][1] = arr[i+1][1];
                    arr[i+1][0] = temp[i][0];
                    arr[i+1][1] = temp[i][1];
                }
            }
        }
        // 다시 회의 시간이 짧은 것 부터 회의들을 지정,
        // 제일 짧은 회의시간들을 기준으로 for문을 돌려서 배열에 저장
        // 회의를 하나 선택할떄마다 count++;
        // 배열에서 count 값이 제일 큰 것이 답.


    }
}

-> 로직 : 회의 시간이 짧은 순서로 정렬 후, 제일 짧은 회의들을 정답 후보군으로 지정,
제일 짧은 회의들을 순서대로 1번쨰로 회의로 지정 후 다음 짧은 회의를 차례대로 넣는 로직.
이렇게 나온 결과들 중 제일 큰 값이 정답

하지만 중간에 생각해보니, 배열을 정렬하고 한 번 더 계산해야 해서 오래 걸린다고 생각해서 방향을 틀었다.

 

2.

종료시간이 빠른걸 먼저 정렬했다.

하지만 버블정렬 자체가 너무 오래걸려서 시간 초과

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        int n = Integer.parseInt(br.readLine());
        int[][] arr = new int[n][2];  // n개의 줄에 각각 2개의 숫자

        // n개의 줄에서 각각 2개의 숫자 입력받기
        for(int i = 0; i < n; i++) {
            String[] input = br.readLine().split(" ");
            arr[i][0] = Integer.parseInt(input[0]);
            arr[i][1] = Integer.parseInt(input[1]);
        }

        int[][] temp = new int[n][2]; // 종료시간이 작은것부터 정렬
        for(int i = 0; i < n-1; i++) {
            for(int j = 0; j < n-1; j++) {
                if(arr[j][1] > arr[j+1][1]){
                    temp[i][0] = arr[j][0];
                    temp[i][1] = arr[j][1];
                    arr[j][0] = arr[j+1][0];
                    arr[j][1] = arr[j+1][1];
                    arr[j+1][0] = temp[i][0];
                    arr[j+1][1] = temp[i][1];
                }
            }
        }
        int end = 0;
        int count = 0;
        for(int i=0; i<n; i++){
            if(arr[i][0] >= end){
                end = arr[i][1];
                count++;
            }
        }
        System.out.println(count);
    }
}

-> 버블정렬을 하니 너무 오래걸림.

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

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        int n = Integer.parseInt(br.readLine());
        int[][] arr = new int[n][2];  // n개의 줄에 각각 2개의 숫자

        // n개의 줄에서 각각 2개의 숫자 입력받기
        for(int i = 0; i < n; i++) {
            String[] input = br.readLine().split(" ");
            arr[i][0] = Integer.parseInt(input[0]); // 시작시간
            arr[i][1] = Integer.parseInt(input[1]); // 종료시간
        }

        Arrays.sort(arr,(a,b)->{
            if(a[1]==b[1]) return a[0]-b[0];
            return a[1]-b[1];
            // return 값이 양수면 뒤에가 앞으로 ( 즉 앞의 것이 더 커서 뒤로 보냄 )
        });
        int end = 0;
        int count = 0;
        // 시작시간이 end보다 같거나 크면, end를 현재 회의의 종료시간으로 설정
        for(int i=0; i<n; i++){
            if(arr[i][0] >= end){ 
                end = arr[i][1];
                count++; // 회의 수 카운트 +1
            }
        }
        System.out.println(count); // 회의의 총 갯수
    }
}

-> 버블정렬 대신 Arrays.sort() 함수를 이용