[자바] 백준 1374 강의실

(엥 누가 분명 하루 한문제 푼다고 한 것 같은데..)

 

근데 정말 최종 프로젝트때문에 바빠서 문제를 풀 시간이 없긴했습니다. 

 

이제는 백수이니까 정말 진심 하루 한문제 풀기 도전합니다? 

 

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

 

- 문제풀이

 

어디서 많이 본 문제입니다.  Job sequencing Algoritm 과 유사한 느낌이지만! 여기서는 스케줄링을 하는 것이 아니라 필요한 최소 강의실의 수를 구해야합니다. 

 

조건 : 1<= N <= 100,000 / startTime, endTime <= 1,000,000,000 / 2sec 

 

직관적인 풀이로 0부터 숫자를 하나씩 증가 시키며 겹치는 강의 수를 카운팅하는 풀이를 생각해봤는데, endTime 의 범위를 보고 빠르게 포기했습니다. O(N  x 10억) 

 

그 다음으로는 모든 강의를 순회하면서, 강의를 넣고 못 넣으면 강의실을 추가하면서 풀어보았습니다. 

 

강의실에 강의를 추가할 수 있는가 조건은 '최근강의 endTime <= 넣을 강의 stratTime" 걸었습니다. 

 

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.List;
import java.util.PriorityQueue;
import java.util.StringTokenizer;

public class Main {
    private static class Lecture implements Comparable<Lecture>{
        int number;
        int start;
        int end;
        Lecture(int number,int start,int end){
            this.number = number;
            this.start = start;
            this.end = end;
        }
        @Override
        public int compareTo(Lecture o1){
            return this.start-o1.start;
        }
    }
    private static class Room{
        int lastEndTime;
        Room(Lecture lecture){
            this.lastEndTime = lecture.end;
        }
        public boolean canAdd(Lecture lecture){
            if(lastEndTime<=lecture.start){
                this.lastEndTime = lecture.end;
                return true;
            }
            return false;
        }
    }
    static int n;
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        n = Integer.parseInt(br.readLine());
        PriorityQueue<Lecture> pq = new PriorityQueue<>();
        List<Room> list = new ArrayList<>();
        StringTokenizer st;
        for(int i=0;i<n;i++){
            st = new StringTokenizer(br.readLine());
            int number = Integer.parseInt(st.nextToken());
            int start = Integer.parseInt(st.nextToken());
            int end = Integer.parseInt(st.nextToken());
            pq.add(new Lecture(number,start,end));
        }
        Loop1:
        while(!pq.isEmpty()){
            Lecture now  = pq.poll();
//            System.out.println(now.start);
            if(list.isEmpty()){
                list.add(new Room(now));
                continue;
            }
            for(Room room : list){
                if(room.canAdd(now)){
                    continue Loop1;
                }
            }
            list.add(new Room(now));
        }
        System.out.println(list.size());
    }
}

 

 

시간초과를 받았습니다 ㅠ

 

N의 한번 탐색은 필수적이니, 두번째 for문에서 비효율이 존재한다고 생각했습니다. 

 

그러고 보니 모든 강의실을 확인하는 것이 아니라 "최근 강의의 endTime이 가장 적은 강의실과 현재 강의 startTime" 만 비교해주면 깔끔해 보였습니다.

 

-코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.List;
import java.util.PriorityQueue;
import java.util.StringTokenizer;

public class Main {
    private static class Lecture implements Comparable<Lecture>{
        int number;
        int start;
        int end;
        Lecture(int number,int start,int end){
            this.number = number;
            this.start = start;
            this.end = end;
        }
        @Override
        public int compareTo(Lecture o1){
            return this.start-o1.start;
        }
    }
    private static class Room implements Comparable<Room>{
        int lastEndTime;
        Room(Lecture lecture){
            this.lastEndTime = lecture.end;
        }
        public boolean canAdd(Lecture lecture){
            if(lastEndTime<=lecture.start){
                this.lastEndTime = lecture.end;
                return true;
            }
            return false;
        }
        @Override
        public int compareTo(Room o1){
            return this.lastEndTime -o1.lastEndTime;
        }
    }
    static int n;
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        n = Integer.parseInt(br.readLine());
        PriorityQueue<Lecture> pq = new PriorityQueue<>();
//        List<Room> list = new ArrayList<>();
        PriorityQueue<Room> pq2 = new PriorityQueue<>();
        StringTokenizer st;
        for(int i=0;i<n;i++){
            st = new StringTokenizer(br.readLine());
            int number = Integer.parseInt(st.nextToken());
            int start = Integer.parseInt(st.nextToken());
            int end = Integer.parseInt(st.nextToken());
            pq.add(new Lecture(number,start,end));
        }
        Loop1:
        while(!pq.isEmpty()){
            Lecture now  = pq.poll();
//            System.out.println(now.start);
            if(pq2.isEmpty()){
                pq2.add(new Room(now));
                continue;
            }
            // 강의실을 문제가 오지게 많이 만들때 극한의 비효율이 발생.
//            for(Room room : list){
//                if(room.canAdd(now)){
//                    continue Loop1;
//                }
//            }
            if(pq2.peek().lastEndTime<=now.start){
                Room room = pq2.poll();
                room.canAdd(now);
                pq2.add(room);
                continue;
            }
            pq2.add(new Room(now));
        }
        System.out.println(pq2.size());
    }
}

 

- 후기

pq를 너무 좋아하는 거 아닐까..요