[SWEA]4408. 자기 방으로 돌아가기 (java)

완전 그리디 문제

import java.util.*;
import java.io.*;
 
class Solution {
    public static void main(String args[]) throws Exception {
 
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int T;
        StringTokenizer st;
        st = new StringTokenizer(br.readLine());
        T = Integer.parseInt(st.nextToken());
 
 
        for (int test_case = 1; test_case <= T; test_case++) {
            st = new StringTokenizer(br.readLine());
            int N = Integer.parseInt(st.nextToken());
            int[][] room = new int[N][2];
            int[] corridor = new int[201];
            for (int i = 0; i < N; i++) {
                st = new StringTokenizer(br.readLine());
                int A = Integer.parseInt(st.nextToken());
                int B = Integer.parseInt(st.nextToken());
                A = A % 2 == 0 ? A : ++A;
                B = B % 2 == 0 ? B : ++B;
                room[i][0] = Math.min(A, B) / 2;
                room[i][1] = Math.max(A, B) / 2;
            }
             
            //시작 방부터 목적 방까지 지나는 복도에 흔적을 남긴다.
            for (int[] cur : room) {
                for (int i = cur[0]; i <= cur[1]; i++) {
                    corridor[i]++;
                }
            }
 
            //제일 많이 지나는 복도에 값이 구하고자 하는 값.
            int answer = Integer.MIN_VALUE;
            for (int cur : corridor)
                answer = Math.max(cur, answer);
 
            System.out.println("#" + test_case + " " + answer);
        }
    }
}

 

import java.util.*;
import java.io.*;
 
class Solution {
 
    public static void main(String args[]) throws Exception {
 
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int T;
        StringTokenizer st;
        st = new StringTokenizer(br.readLine());
        T = Integer.parseInt(st.nextToken());
 
        for (int test_case = 1; test_case <= T; test_case++) {
            st = new StringTokenizer(br.readLine());
            int N = Integer.parseInt(st.nextToken());
            Dot[] arr = new Dot[N];
            for (int i = 0; i < N; i++) {
                st = new StringTokenizer(br.readLine());
                int A = Integer.parseInt(st.nextToken());
                int B = Integer.parseInt(st.nextToken());
                A = A % 2 == 1 ? ++A : A;
                B = B % 2 == 1 ? ++B : B;
                if (A > B) {
                    arr[i] = new Dot(B, A);
                } else
                    arr[i] = new Dot(A, B);
            }
            Arrays.sort(arr);
 
            int answer = 0;
            boolean[] marked = new boolean[N];
 
            while (true) {
                boolean flag = false;
                for(boolean mark : marked) if(!mark) flag = true;
                if(!flag) break;
                int end = 0;
                
                for (int i = 0; i < N; i++) {
                    //이미 지났다면 또 지나지 않는다.
                    if(marked[i]) continue;
                    //현재 방에서 출발할 때 다음 방의 시작 방과 겹치지 않는다면?
                    if(arr[i].start > end) {
                        end = arr[i].end;
                        marked[i] = true;
                    }
                }
                answer++;
            }
            System.out.println("#" + test_case + " " + answer);
        }
    }
 
    static class Dot implements Comparable<Dot> {
        int start;
        int end;
 
        Dot(int start, int end) {
            this.start = start;
            this.end = end;
        }
 
        @Override
        public int compareTo(Dot o) {
            if (this.start == o.start)
                return this.end - o.end;
            return this.start - o.start;
        }
    }
}