[백준] 단계별로 풀어보기(단계:16,그리디 알고리즘,JAVA)1931번, 회의실 배정

문제 링크

1931번: 회의실 배정

 

www.acmicpc.net

---

주의사항

• JAVA를 사용하여 프로그램을 사용하였습니다.
• 백준에서 코드를 작성하였을 때 아래 형태에서 Main에서 결과가 출력되어야 합니다.

public class Main{ 	
	public static void main(String[] args){
    }
}

---

문제 설명

---

접근 방법

그리드 알고리즘(탐욕 알고리즘)이란 여러 경우를 선택해야할 때 그 상황에 최적의 경우으로 생각하는 것을 반복하여 최종적인 답을 가져오는 방법입니다.

 

이 문제에서는 최대의 회의실 사용횟수를 구하려면 현재 시간에서 최소로 끝날 수 있는 시간을 찾아서 그 회의를 반복하는 것입니다.

문제에서는 회의의 시작시간과 끝나는 시간이 섞여있기 때문에 끝나는 시간 순으로 오름차순 정렬을 하였습니다.

만약 끝나는 시간이 같다면 시작시간을 내림차순으로 정렬하였습니다.

• 회의실에 시작 시간과 끝나는 시간을 저장할 배열 room를 만들었습니다.
• BufferedReader를 사용하여 입력 값을 받았습니다.
• StringTokenizer를 사용하여 입력값을 띄어쓰기로 나누어 시작 시간과 끝나는 시간을 저장하였습니다.
• 회의 최대 횟수를 계산하는함수 meetingRoom을 만들었습니다.
• BufferedWriter을 사용하여 최대값을 출력하였습니다.

• 정렬되었기 때문에 순차적으로 반복하여 현재 시간이 시작시간보다 크거나 같으면 회의실을 사용할 수 있기 때문에 현재 시간에 그 회의실에 끝나는 시간으로 적용되는 것을 반복하도록 하였습니다.
• for문이 종료되면 최대값을 반환하도록 하였습니다.

결과 코드

import java.io.*;
import java.util.*;
public class Main{
	static int[][] room;	//회의실 시간 저장 배열
	public static void main(String[] args) throws IOException{
    	BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        //BufferedReader를 통해 입력 값 받기
    	BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
    	//BufferedWriter를 통해 결과 값 출력
        //---------입력값 저장 및 배열 초기화-------------
    	StringTokenizer st;
    	int index = Integer.parseInt(br.readLine());
    	room = new int[index][2];
    	for(int i=0;i<index;i++) {
    		st = new StringTokenizer(br.readLine()," ");
    		room[i][0] = Integer.parseInt(st.nextToken());
    		room[i][1] = Integer.parseInt(st.nextToken());
    	}
        //---------------배열 정렬----------
    	Arrays.sort(room,new Comparator<int[]>(){
    		@Override
    		public int compare(int[] o1, int[] o2) {
    			if(o1[1]==o2[1])	//끝나는 시간 같을 때 시작 시간 기준 정렬
    				return o1[0]-o2[0];
    			return o1[1] - o2[1];	//끝나는 시간 정렬
    		}
		});
    	
    	bw.write(meetingRoom(index) + "\n");	//함수 결과 출력
    	bw.flush();
    	bw.close();
    	br.close();
	}
    //------------회의실 사용횟수 최대값 구하는 함수-------------
	public static int meetingRoom(int index) {
		int currentTime = room[0][1];	//현재 시간
		int result=1;	//회의실 사용 횟수
		for(int i=1;i<index;i++) {
			if(room[i][0]>=currentTime) {	//다른 회의실 사용
				result++;
				currentTime = room[i][1];
			}
		}
		return result;	//결과 반환
	}
}