[알고리즘풀이]백준 1931: 회의실 배정 JAVA

목차

• 개요
•  본문
•  1) 문제
•  2) 과정
•  3) 코드 전체

 

 

개요

이전에 알고리즘 스터디에서 JAVA를 이용해 백준 1931번 회의실 배정을 풀었습니다. 이를 정리해보고자 합니다.

1931번: 회의실 배정

 

본문

1) 문제

 

2) 과정

푸는데 꽤 시간이 들었던 문제였습니다. 1시간에서 2시간 정도 시간이 들었던 것 같네요!

이번엔 main에서 input과 func를 불러 실행이 되도록 했는데, 이번엔 Time이라는 클래스를 만들어 한 회의의 시간 타임을 사용할 수 있도록 했습니다.

 

2-1) main

    // Attribute
    private static int n;
    private static Time[] timeArr;
    
    // Main
    public static void main(String[] args) throws IOException {
       input();
       func();
    }

main은 다음과 같이 입력값을 받는 input과 계산을 수행하는 func로 구성하였습니다. 

 

전역변수로 선언된 변수 n, timeArr은 각각 회의 수, ,회의 정보를 담은 배열입니다.

 

2-2) Input

    private static void input() throws IOException {
        // Input
        BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));
        n=Integer.parseInt(reader.readLine());
        timeArr = new Time[n];

        for(int i=0;i<n;i++) {
            String[] strings = reader.readLine().split(" ");
            timeArr[i]=new Time(Integer.parseInt(strings[0]),Integer.parseInt(strings[1]));
        }
        
        // Initialize
        Arrays.sort(timeArr);

    }

 

읽어오는 것 관련된 정보는 아래 링크를 확인해주세요 :)

[개념정리] System.in / InputStreamReader / BufferedReader 정리

첫번째 줄을 읽어 n에 값을 넣어줍니다. 이후 n의 크기로 int배열 timeArr에 값을 읽어 넣어줍니다. 그리고 timeArr을 정렬해주는데 이때 Time의 compareTo가 종료시간이 다를 경우 종료시간을 기준으로 비교하고, 같을 경우 시작시간을 비교하도록 하여 timeArr의 Time객체들은 종료시간을 주 기준으로 정렬됩니다.

 

2-3) Logic

    // Logic
    private static void func(){
        // Local variable
        int afterTime=0, count=0;
        
        // Logic
        for(int i=0;i<n;i++){
            if(afterTime<=timeArr[i].getStartTime()) {
                afterTime = timeArr[i].getFinishTime();
                count++;
            }
        }
        
        // Output
        System.out.println(count);
    }

Logic부분은 지역변수를 선언하는 부분과 실질적인 로직부분, 출력부분으로 구성됩니다.

 

지역변수를 선언하는 부분은 2개의 변수를 선언하며 시작됩니다. 이 때의 afterTime, count는 각각 최근에 넣어진(더 늦은 시간에 시작되는) 회의, 회의의 수입니다.

 

그리고 실질적인 로직 부분에서는 정렬된 timeArr에서 값을 받아오며 afterTime에 있는 회의종료 시간보다 timeArr의 회의 시작시간이 더 늦다면, timeArr의 회의의 종료시간을 afterTime으로 바꾸고 회의수를 의미하는 count에 1을 더해줍니다. 이 방식이 가능한 것은 timeArr가 위의 Input에서 말씀드린 방식으로 정렬되어있기 때문인 점을 유의해서 문제를 푸셔야합니다..!

 

그렇게 Output에서는 가능한 최대 회의 수를 출력하며 실행이 종료됩니다.

 

2-4) Time 클래스

    private static class Time implements Comparable {

        private final int startTime;
        private final int finishTime;

        // get & set
        public int getStartTime() {return startTime;}
        public int getFinishTime() {return finishTime;}

        // Constructor
        public Time(int startTime, int finishTime){
            this.finishTime = finishTime;
            this.startTime = startTime;
        }

        @Override
        public String toString() {return startTime+" "+finishTime;}

        @Override
        public int compareTo(Object o) {
            Time t = (Time)o;
            if (this.finishTime==t.finishTime) return this.startTime - t.startTime;
            else return this.finishTime-t.finishTime;
        }
    }

 

 

Time클래스는 다음과 같습니다. 그저 시작시간, 종료시간, 그리고 각 시간을 비교할 compareTo, 출력시 보일 값을 정해두는 toString을 담고 있습니다.

 

3) 전체코드

그렇게 완성된 코드는 다음과 같습니다.

package sujeong.greedy;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;

public class BOJ1931 {
    private static class Time implements Comparable {

        private final int startTime;
        private final int finishTime;

        // get & set
        public int getStartTime() {return startTime;}
        public int getFinishTime() {return finishTime;}

        // Constructor
        public Time(int startTime, int finishTime){
            this.finishTime = finishTime;
            this.startTime = startTime;
        }

        @Override
        public String toString() {return startTime+" "+finishTime;}

        @Override
        public int compareTo(Object o) {
            Time t = (Time)o;
            if (this.finishTime==t.finishTime) return this.startTime - t.startTime;
            else return this.finishTime-t.finishTime;
        }
    }
    
    // Variable
    private static int n;
    private static Time[] timeArr;

    // Input & Initialize
    private static void input() throws IOException {
        // Input
        BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));
        n=Integer.parseInt(reader.readLine());
        timeArr = new Time[n];

        for(int i=0;i<n;i++) {
            String[] strings = reader.readLine().split(" ");
            timeArr[i]=new Time(Integer.parseInt(strings[0]),Integer.parseInt(strings[1]));
        }
        
        // Initialize
        Arrays.sort(timeArr);

    }

    // Logic
    private static void func(){
        // Local variable
        int afterTime=0, count=0;
        
        // Logic
        for(int i=0;i<n;i++){
            if(afterTime<=timeArr[i].getStartTime()) {
                afterTime = timeArr[i].getFinishTime();
                count++;
            }
        }
        
        // Output
        System.out.println(count);
    }

    // Main
    public static void main(String[] args) throws IOException {
       input();
       func();
    }
}

 

깃헙으로 더 자세히 보고싶으시다면, 아래 링크를 참고해주세요 :)

https://github.com/Park1122/Algorithm-Study/blob/master/sujeong/greedy/BOJ1931.java

GitHub - Park1122/Algorithm-Study: 명지대학교 학생들이 모여서 만든 알고리즘 공부 및 코딩테스트 준비