BOJ_7507 : 올림픽 게임

👉 문제링크

7507번: 올림픽 게임

---

---

🔸 문제 분석 🔸

• 문제
  • 한 경기가 끝나야 다음 경기를 볼 수 있다. 
  • 종료와 시작 시간이 완전히 같아도 볼 수 있다.
  • 테스트 케이스 별, 한 사람이 볼 수 있는 최대 경기 수를 출력한다.
• 풀이 (Greedy)
  • 경기 정보를 날짜와 종료 시간으로 오름차순 정렬 한다.
  • 다음 경기를 볼 수 있으면 카운트 + 1을 한다.
    • 다음 경기가 다음 날짜이면, 무조건 볼 수 있으므로 다음 경기로 이동한다.
    • 다음 경기의 시작이 현재 경기의 종료 시간보다 같거나 크면, 볼 수 있는 경기이므로 다음 경기로 이동한다.
  • 그 외는 볼 수 없는 경기이다.
  • 마지막 경기까지 확인하면, 카운트를 출력한다.

🔸 코드 🔸

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));
        StringBuilder sb = new StringBuilder();

        // 1) Test Case
        int n = Integer.parseInt(br.readLine());
        for (int t = 1; t <= n; t++) {
            // 2) Input
            int m = Integer.parseInt(br.readLine());

            Game[] games = new Game[m];

            for (int i = 0; i < m; i++) {
                StringTokenizer st = new StringTokenizer(br.readLine());
                games[i] = new Game(Integer.parseInt(st.nextToken()), st.nextToken(), st.nextToken());
            }

            // 3) Sort
            Arrays.sort(games);

            // 4) Greedy
            int answer = 1;
            Game game = games[0];
            for (int i = 1; i < m; i++) {
                if (game.day != games[i].day || game.end.compareTo(games[i].start) <= 0) {
                    game = games[i];
                    answer++;
                }
            }

            // 5) Output
            sb.append(String.format("Scenario #%d:\n%d\n\n", t, answer));
//            print(games, dp);
        }
        System.out.println(sb);
    }

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

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

        @Override
        public int compareTo(Game o) {
            if (this.day != o.day)
                return this.day - o.day;
            return this.end.compareTo(o.end);
        }
    }
}

🔸 코드 해석 🔸

• Game이라는 클래스를 만들어, 날짜, 시작시간, 종료시간을 저장한다.
  • Comparable 인터페이스를 상속해, 날짜와 종료시간으로 정렬할 수 있도록 한다.
• 1) 2) 테스트케이스 마다 경기 정보를 입력받고, 정렬한다.
• 3) 날짜, 종료시간을 오름차순으로 정렬한다.
• 4) 그리디 알고리즘으로 관람 가능한 경기 수 answer를 카운트한다.
  • 정렬한 경기 정보를 순회한다.
  • 현재 경기( game )와 다음 경기( game[i] )를 비교한다.
    • 날짜가 달라지거나, 다음 경기의 시작 시간이 현재 경기의 시작 시간보다 크거나 같으면,
      다음 경기를 현재 경기로 저장하고, answer를 +1 한다.
• 5) 경기 수를 출력한다.

🔸 오답 코드 : Dynamic Programming 🔸

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));
        StringBuilder sb = new StringBuilder();

        // 1) Test Case
        int n = Integer.parseInt(br.readLine());
        for (int t = 1; t <= n; t++) {
            // 2) Input
            int m = Integer.parseInt(br.readLine());
            int[] dp = new int[m];
            dp[0] = 1;

            Game[] games = new Game[m];

            for (int i = 0; i < m; i++) {
                StringTokenizer st = new StringTokenizer(br.readLine());
                games[i] = new Game(Integer.parseInt(st.nextToken()), st.nextToken(), st.nextToken());
            }

            // 3) Sort
            Arrays.sort(games);

            // 4) dp
            int max = 0;
            for (int i = 1; i < m; i++) {
                dp[i] = find_Before_Game(games, dp, i);
                max = Math.max(max, dp[i]);
            }

            // 5) Output
            sb.append(String.format("Scenario #%d:\n%d\n\n", t, max));
//            print(games, dp);
        }
        System.out.println(sb);
    }

    private static int find_Before_Game(Game[] games, int[] dp, int now) {
        for (int i = now - 1; i >= 0; i--) {
            if (games[now].day > games[i].day ||
                    games[now].start.compareTo(games[i].end) >= 0) {
                return dp[i] + 1;
            }
        }
        return 1;
    }


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

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

        @Override
        public int compareTo(Game o) {
            if (this.day != o.day)
                return this.day - o.day;
            return this.start.compareTo(o.start);
        }
    }

    private static void print(Game[] games, int[] dp) {
        System.out.println("\n=============================\n");
        System.out.println("\n# n : day\tstart\tend \tdp");
        for (int i = 0; i < games.length; i++) {
            System.out.printf("# %d : %d \t%s\t%s\t%d\n",
                    i, games[i].day, games[i].start, games[i].end, dp[i]);
        }
        System.out.println("\n=============================\n");
    }
}

• DP를 이용한 풀이다.
• 각 경기의 인덱스와 매칭되는 dp 배열을 만든다.
• 해당 경기를 포함해 최대로 볼 수 있는 경기 수를 원소로 저장한다.
  • 현재 경기 이전의 경기 정보를 역순으로 찾으며, 이어서 볼 수 있는지 확인한다.
  • 이어서 볼 수 있으면, 찾은 경기의 인덱스dp값 +1을 저장한다.
  • 볼 수 있는 경기가 없으면 1을 저장한다.
• m이 50000(5만)으로 커서 시간초과가 난다.

---

🔸 end 🔸

• dp로 열심히 풀고 테스트 케이스도 5만개 까지 만들었는데, 최종 제출에서 시간 초과가 나서 좌절했다...
  • 심지어 입출력 등을 최적화 해봐도 마찬가지였다.
  • 풀이 포스팅을 찾아보고 그리디로 풀이를 변경했는데 너무 간단했다.
• 비록 틀렸지만 문제 분석과 코딩 계획을 적어가며 풀이했다.
• 태그가 없어서 기여하기로 greedy와 sort를 넣었더니 문제에 표시됐다.
• 테스트 케이스도 공유했다.