백준 7507 - 올림픽 게임 (자바 - 그리디)

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

7507번: 올림픽 게임

 

* 문제 요약

상근이는 올림픽을 매우 좋아하면서 싫어한다. 올림픽을 좋아하는 이유는 많은 스포츠 경기를 볼 수 있기 때문이고, 싫어하는 이유는 경기가 동시에 열리기 때문이다.

방금 올림픽이 열리는 장소에 도착을 했다. 하지만, 경기가 동시에 열리기 때문에, 상근이는 모든 경기를 실시간으로 볼 수 없다.

모든 경기의 시작 시간과 종료 시간, 그리고 날짜가 주어진다. 이때, 상근이가 볼 수 있는 경기의 최대 갯수를 구하는 프로그램을 작성하시오.

상근이는 경기장에 시작 시간에 들어가며, 종료 시간에 나오게 된다. 한 경기를 보던 중에 다른 경기를 보기 위해 경기장을 옮길 수 없다.

또, 경기장을 이동하는데 걸리는 시간은 없다. 마지막으로 경기가 시작된 이후에는 경기장에 들어갈 수 없다.

 

* 입력

첫째 줄에는 테스트 케이스의 갯수 n 이 주어진다.

각 테스트 케이스의 첫째 줄에는 경기의 수 1 <= m <= 50,000 이 주어진다.

다음 m 개의 줄에는 각 경기의 정보를 나타내는 정수 d, s, e 가 주어진다.

d 는 경기의 날짜, s 는 시작 시간, e 는 종료 시간을 나타낸다.

시간은 hhmm 형식으로 주어지며, 모든 경기는 시작한 날에 끝난다.

 

* 출력

각 테스트 케이스마다 Scenario #i: 를 출력한다. 여기서 i 는 테스트 케이스 번호이며 1 부터 시작한다.

그 다음 줄에는 상근이가 참석할 수 있는 경기의 최대 갯수를 출력한다.

문제에서도 설명했지만, 경기장을 이동하는데 걸리는 시간은 없다. 즉, 경기 A 의 종료 시간이 B 의 시작 시간과 같은 경우에 상근이는 A 이후에 바로 B 로 이동할 수 있다.

각 테스트 케이스 사이에는 빈 줄을 하나 출력한다.

 

* 예시

 

* 해결 과정

올림픽에서 시행되는 경기의 날짜, 시작 시간, 종료 시간 데이터를 저장하는 객체 Game 을 만들어 준 후 Comparable 인터페이스를 직접 구현하여 정렬 로직을 날짜, 시작 시간, 종료 시간에 따라 오름차순 정렬하게끔 compareTo() 메소드를 새로 오버라이딩 해주었다.

 

이후 입력받은 데이터를 Arrays.sort() 메소드를 통해 오름차순 정렬해준 다음 데이터의 가장 마지막. 즉, 경기가 열리는 날짜와 시작 시간, 종료 시간이 가장 늦는 경기부터 순차적으로 탐색하며 아래와 같은 로직을 수행하였다.

자료구조는 현재 탐색중인 경기와 마지막으로 탐색했던 경기를 쉽게 비교할 수 있도록 스택 자료구조를 활용하였다.

 

1. 스택이 비어있다면 현재 탐색중인 경기 데이터를 즉시 스택에 넣는다.

2. 스택이 비어있지 않은 경우 다음과 같은 로직을 수행한다.

2-1. 스택에 마지막으로 넣은 경기와 현재 탐색중인 경기를 아래와 같이 비교한 후 로직을 수행한다.

    - 스택에 마지막으로 넣은 경기가 열리는 날짜가 현재 탐색중인 경기의 날짜보다 늦는 경우 현재 탐색중인 경기 데이터를 스택에 넣는다.

    - 만약 그렇지 않을 경우 스택에 마지막으로 넣은 경기가 열리는 시작 시간과 현재 탐색중인 경기의 종료 시간을 비교하여, 시작 시간이 더 늦는 경우 현재 탐색중인 경기 데이터를 스택에 넣는다.

3. 위와 같은 과정을 거쳐 배열을 뒤에서부터 앞까지 모두 탐색하고 나면 현재 스택의 크기를 결과 출력을 위한 배열에 저장해 준 후 다음 테스트 케이스에 대해 로직을 수행한다.

4. 모든 테스트 케이스에 대해 로직 수행이 끝나면 문제에서 제시한 규칙대로 정답들을 순서대로 출력해준다.

 

* 코드

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.Arrays;
import java.util.Stack;

public class Main {
    public static void main(String[] args) throws NumberFormatException, IOException {
        new Main().solution();
    }

    private void solution() throws NumberFormatException, IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

        int count = Integer.parseInt(br.readLine());
        int[] resultArray = new int[count];
        for (int i = 0; i < count; i++) {
            int gameCount = Integer.parseInt(br.readLine());
            int result = 0;
            Game[] gameArray = new Game[gameCount];
            for (int j = 0; j < gameCount; j++) {
                String[] input = br.readLine().split(" ");

                int day = Integer.parseInt(input[0]);
                int start = Integer.parseInt(input[1]);
                int end = Integer.parseInt(input[2]);

                Game game = new Game(day, start, end);
                gameArray[j] = game;
            }

            Arrays.sort(gameArray);

            Stack<Game> gameStack = new Stack<>();
            for (int j = gameArray.length - 1; j >= 0; j--) {
                if (gameStack.isEmpty()) {
                    gameStack.push(gameArray[j]);
                } else {
                    Game after = gameStack.peek();
                    Game before = gameArray[j];

                    if (after.day > before.day) {
                        gameStack.push(before);
                    } else {
                        if (after.start >= before.end) {
                            gameStack.push(before);
                        }
                    }
                }
            }

            result = gameStack.size();
            resultArray[i] = result;
        }

        int number = 1;
        for (int i : resultArray) {
            bw.write("Scenario #" + number + ":\n" + i + "\n\n");
            number++;
        }
        bw.flush();
        bw.close();
        br.close();
    }
}

class Game implements Comparable<Game> {
    int day;
    int start;
    int end;

    public Game(int day, int start, int end) {
        this.day = day;
        this.start = start;
        this.end = end;
    }

    @Override
    public int compareTo(Game arg0) {
        if (this.day == arg0.day) {
            if (this.start == arg0.start) {
                return this.end - arg0.end;
            } else {
                return this.start - arg0.start;
            }
        } else {
            return this.day - arg0.day;
        }
    }
}

 

현재 상황에서 최적의 해답을 선택한다. -> 경기 데이터들을 정렬해준 배열을 대상으로 경기 날짜, 시작 시간, 종료 시간이 가장 늦는 경기부터 탐색을 시작해, 마지막으로 탐색한 경기, 현재 탐색중인 경기를 서로 비교하여 시간이 겹치지 않는 경우 현재 탐색중인 경기 또한 볼 수 있다는 뜻이므로 현재 탐색중인 경기 데이터를 스택에 넣어준다.

선택된 해답이 조건을 만족하는지 검사한다. -> 배열에 대한 탐색이 모두 끝날때까지 모든 경기에 대해 최대로 많이 볼 수 있는 경기 숫자를 특정할 수 없으므로 배열 끝까지 탐색을 진행한다.

 

위의 과정을 통해 문제를 해결하였으므로 그리디 알고리즘에 해당된다.