백준 1931 풀이

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

이번 문제는 회의실 시간표를 짜는 문제이다.

예전에 카카오 코딩테스트에 이러한 비슷한 문제가 나온적 있었는데...

물론 이 문제보단 어려웠지만 그 때는 감도 잡지 못하던걸 이번엔 그리디로 풀면 되겠다는 점은 금방 알아챌 수 있었다. ㅠㅠ

그리디로 풀면 되겠다는 점을 알아차려도 어느 것을 기준으로 삼아 먼저 채택할지 고민이 있었는데 회의시간을 최대한 활용하려면 끝나는 시간이 빠른 것부터 선택하여 이어지게 선택하면 되겠다는 생각을 했다.

또한 문제에서 시작시간과 끝나는 시간이 같을 수 있고 회의가 연달아 이루어질 수도 있다고 했기때문에 정렬이 필요했다.

위의 생각으로 코드를 작성했고 정답을 찾았다.

import java.io.*;
import java.util.ArrayList;

public class Main {

    public static void main(String[] args) throws IOException {
        // write your code here
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        String num = br.readLine();
        int n = Integer.parseInt(num);
        ArrayList<Pair> list = new ArrayList<>();
        ArrayList<Pair> answer = new ArrayList<>();
        for (int i = 0; i < n; i++) {
            String tmp = br.readLine();
            String[] nums = tmp.split(" ");
            Pair p = new Pair(Integer.parseInt(nums[0]), Integer.parseInt(nums[1]));
            list.add(p);
        }


        list.sort(Pair::compareTo);
        /*for (Pair p : list) {
            System.out.println(p.first + " " + p.second);
        }*/
        answer.add(list.get(0));
        for (int i = 1; i < list.size(); i++) {
            Pair p = list.get(i);
            Pair q = answer.get(answer.size() - 1);
            if (q.second <= p.first)
                answer.add(p);
        }

        bw.write(Integer.toString(answer.size()));

        br.close();
        bw.close();
    }
}

class Pair implements Comparable<Pair> {
    public int first;
    public int second;

    public Pair() {
    }

    public Pair(int a, int b) {
        this.first = a;
        this.second = b;
    }

    @Override
    public int compareTo(Pair o) {
        if (this.second < o.second)
            return -1;
        else if (this.second == o.second) {
            if (this.first < o.first) {
                return -1;
            }
            else
                return 1;
        } else
            return 1;
    }
}

단순한 문제였지만 그리디 문제를 푸는데 익숙하지 못해 감을 잡는데 오래 걸렸다...