[코딩테스트] Java_ 백준 1931번 회의실 배정 문제풀이(그리디 알고리즘) - Rowen Jobs

백준 1931번 회의실 배정 문제풀이

 

우선 종료시간만 고려하다가 계속 에러가 나서 시작시간도 정렬 해주어 진행하였습니다. 

 

필요 알고리즘 

- 그리디(탐욕) 알고리즘

- 정렬

 

회의실 배정 성공

 

시간 제한메모리 제한제출정답맞힌 사람정답 비율

2 초

128 MB

182093

58235

40747

29.999%

문제

한 개의 회의실이 있는데 이를 사용하고자 하는 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) 를 이용할 수 있다.

출처

• 빠진 조건을 찾은 사람: andy627
• 데이터를 추가한 사람: jws0324, kimchangyoung, rosedskim

알고리즘 분류

• 그리디 알고리즘
• 정렬

 

코드는 아래 주석과 함께 작성하였습니다.

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

public class Main {
    public static void main(String[] args) throws IOException {
    	// 입력값 받을 준비
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        
        // 회의 갯수 
        int meeting_cnt = Integer.parseInt(st.nextToken());
        // 회의 시작-종료 이중 배열 준비
        int[][] time_array = new int[meeting_cnt][2];
        // 결과값 1 인 이유는 While 문에서 처음 시작할때 카운트를 하지 않아 1로 초기화
        int result = 1;
		
        // 이중배열 셋팅
        for(int i = 0; i < meeting_cnt; i++) {
            StringTokenizer st2 = new StringTokenizer(br.readLine());
            for(int j = 0; j < 2; j++){
                time_array[i][j] = Integer.parseInt(st2.nextToken());
            }
        }

		// 여기서 아주 중요! 이중배열의 끝 자리(종료시간) 오름차순으로 정렬을 하는데 
        // 끝 자리(종료시간)들이 같은 숫자일 경우에는 앞 자리(시작시간) 오름차순 정렬 필수! 
        // 왜냐면 문제에 종료시간과 시작시간이 같은 경우도 체크를 해줘야 함.
        Arrays.sort(time_array, (o1, o2) -> {
          return o1[1] == o2[1] ? o1[0] - o2[0] : o1[1] - o2[1];
        });
        
        // 반복문 돌려서 결과값 추출 
        int i = 0;
        int j = 1;
        while (j != meeting_cnt){
            int end_time = time_array[i][1];
            if(time_array[j][0] >= end_time){
                end_time = time_array[j][1];
                result++;
                i = j;
            }
            j++;
        }
        System.out.println(result);
    }
}

 

그리디(탐욕) 알고리즘에 대해서 간단하게 설명을 잘해준 영상이 있어 공유합니다.