[백준/BOJ] 1931번 : 회의실 배정 - Java(자바)

 

 

https://www.acmicpc.net/problem/1931

1931번: 회의실 배정

 

 

---

 

그리디 알고리즘을 사용하는 문제이다.

 

정렬을 생각하지 않고, 바로 그리디하게 풀었다

 

import java.io.*;
import java.util.StringTokenizer;

class Main {

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st;
        int n = Integer.parseInt(br.readLine()), reservedEndTime = 0, cnt = 0;

        for (int i = 0; i < n; i++) {
            st = new StringTokenizer(br.readLine(), " ");
            int startTime = Integer.parseInt(st.nextToken()), endTime = Integer.parseInt(st.nextToken());

            if (startTime >= reservedEndTime) {
                reservedEndTime = endTime;
                cnt++;
            }
        }
        System.out.println(cnt);
    }
}

 

틀렸다.

 

 

 

 

그래서 endTime에 맞춰서 정렬을 했다.

 

import java.io.*;
import java.util.Arrays;
import java.util.Comparator;
import java.util.StringTokenizer;

class Main {

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st;
        int n = Integer.parseInt(br.readLine());
        int[][] meetingHour = new int[n][2];

        for (int i = 0; i < n; i++) {
            st = new StringTokenizer(br.readLine(), " ");
            meetingHour[i][0] = Integer.parseInt(st.nextToken());
            meetingHour[i][1] = Integer.parseInt(st.nextToken());
        }

        Arrays.sort(meetingHour, new Comparator<int[]>() {
            @Override
            public int compare(int[] o1, int[] o2) {
                return o1[1] - o2[1];
            }
        });

        int cnt = 0;
        int reservedEndTime = 0;

        for (int i = 0; i < n; i++) {
            if (meetingHour[i][0] >= reservedEndTime) {
                reservedEndTime = meetingHour[i][1];
                cnt++;
            }
        }
        System.out.println(cnt);
    }
}

 

틀렸다.

 

 

5

4 4

3 4

2 4

1 4

 

와 같은 케이스가 들어오면, [1, 4], [2, 4], ... , [4, 4]로 정렬이 되어야 하지만,

[4, 4], [3, 4], ... , [1, 4]로 정렬되었기 때문이었다.

 

 

그래서 endTime이 같을 경우에는 startTime에 맞춰 정렬하도록 했다.

 

import java.io.*;
import java.util.Arrays;
import java.util.Comparator;
import java.util.StringTokenizer;

class Main {

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st;
        int n = Integer.parseInt(br.readLine());
        int[][] meetingHour = new int[n][2];

        for (int i = 0; i < n; i++) {
            st = new StringTokenizer(br.readLine(), " ");
            meetingHour[i][0] = Integer.parseInt(st.nextToken());
            meetingHour[i][1] = Integer.parseInt(st.nextToken());
        }

        Arrays.sort(meetingHour, new Comparator<int[]>() {
            @Override
            public int compare(int[] o1, int[] o2) {
                if (o1[1] == o2[1]) {
                    return o1[0] - o2[0];
                }
                return o1[1] - o2[1];
            }
        });

        int cnt = 0;
        int reservedEndTime = 0;

        for (int i = 0; i < n; i++) {
            if (meetingHour[i][0] >= reservedEndTime) {
                reservedEndTime = meetingHour[i][1];
                cnt++;
            }
        }
        System.out.println(cnt);
    }
}

 

맞았다.

 

 

그리디 알고리즘은 '언제나 주어진 입력의 순서를 조작하지 않고 풀어야 하지 않을까?' 라는 생각이 있었다.

그래서 내게 더 까다롭게 느껴졌던 것 같다.

 

잘못된 생각을 바꾸고, 배워나갈 수 있었던 좋은 문제였다.