[백준] 1931번 회의실 배정 JAVA (자바) 풀이

문제 1931(그리디, 정렬)

 :  한 개의 회의실, N개의 회의, 회의실 사용표

 :  각 회의 I에 대해 시작시간과 끝나는 시간

    각 회의가 겹치지 않게 하면서 회의실을 사용할 수 있는 회의의 최대 개수 찾기

 

 :  회의는 시작하면 중간에 중단될 수 없으며 한 회의가 끝나는 것과 동시에 다음 회의 시작

    (회의의 시작시간과 끝나는 시간이 같다면 시작하자마자 끝나는 회의)

 

 

[입력]

 :  첫째 줄에 회의의 수 N(1 ≤ N ≤ 100,000)

 :  둘째 줄부터 N+1 줄까지 각 회의의 시작시간과 끝나는 시간

    (시작 시간과 끝나는 시간은 2³¹-1보다 작거나 같은 자연수 또는 0)

  

 

 [출력]

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

 

 

 [문제접근]

 

 1. 정렬 이용하기

• if(a[1]==b[1])  /  return a[0] - b[0];
  종료 시간이 같다면 시작이 먼저인 회의부터 오름차순
  
  
• else  /  return a[1] - b[1];
  종료시간이 다르거나 시작 시간이 같다면 종료가 빨리 끝나는 회의부터 오름차순

 

 2. 회의가 시작되면 언제 끝나는지 기록

• 다음 시작할 회의가 마지막 회의 종료시점과 같거나 이후라면 그회의 시작하고 종료시간 갱신
• 회의 카운트

 

 

 [코드]

import java.io.*;
import java.util.*;
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 time[][] = new int[N][2];
        
        for(int i=0; i<N; i++){
            StringTokenizer st = new StringTokenizer(br.readLine());
            time[i][0]=Integer.parseInt(st.nextToken());
            time[i][1]=Integer.parseInt(st.nextToken());
        }
        
        Arrays.sort(time, (a, b)->{
            if(a[1]==b[1]){
                return a[0] - b[0];
            }
            else{
                return a[1] - b[1];
            }
        });
        
        int result = 0;
        int endTime = 0;
        
        for(int[] t:time){
            if(t[0] >= endTime){
                endTime = t[1];
                result++;
            }
        }
        
        System.out.println(result);
        
    }
}

 

 [해설]
     

 :  BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    int N = Integer.parseInt(br.readLine());  회의실 시간
    int time[][] = new int[N][2];  회의 시간 배열
        
 :  for(int i=0; i<N; i++){
            StringTokenizer st = new StringTokenizer(br.readLine());
            time[i][0]=Integer.parseInt(st.nextToken());  시작시간
            time[i][1]=Integer.parseInt(st.nextToken());  종료시간
    }
        
 :  Arrays.sort(time, (a, b)->{  조건에 맞게 정렬
            if(a[1]==b[1]){  종료시점 같으면
                return a[0] - b[0];  시작 지점 기준 오름차순
            }
            else{  종료시점 다르면
                return a[1] - b[1];  종료가 빠른애로 오름차순
            }
    });
        
 :  int result = 0;  출력할 카운트
    int endTime = 0;  마지막 회의실 이용 시간
        
 :  for(int[] t:time){  정렬된 시간을 기준으로
            if(t[0] >= endTime){  마지막 이용 시간대가 새로운 회의 시작 시간과 같거나 이상이면
                endTime = t[1];  해당 회의 시작하고 종료시간 갱신
                result++;  회의 카운트
            }
    }
        
 :  System.out.println(result);  출력
  


 

 

이제 풀어보러 갈께요 :)

 

* 독학으로 익히는 코딩이라 틀린 것이 있을 수 있습니다. 오류가 있다면 댓글을 통해 알려주세요. 감사합니다. *