[백준] 1931 회의실배정 - 탐욕법(Greedy) + 정렬(Sort) JAVA

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

1931번: 회의실 배정

코드설명

탐욕법(Greedy) + 정렬(Sort) 을 활용합니다.

 

이 문제에서 핵심은, 끝나는 시간이 가장 빠르고, 끝나는 시간이 같다면 시작시간이 빠른 회의실을 차례차례 진행하는 것 입니다.

이떄 처음에 시작시간이 빠른 것은 고려하지 못하여 90%쯤에서 계속해서 틀렸습니다.

3
4 4
3 4
2 4

my output : 1
answer : 2

코드

정답코드 1입니다. Comparable을 활용하여 정렬했습니다. 직접 Comparable Interface를 구현한 모습이지요.

//Comparable 인터페이스를 implements합니다.
class Conference implements Comparable<Conference>{
	
	private int starttime;
	private int endtime;
	
	public Conference(int starttime,int endtime) {
		this.starttime = starttime;
		this.endtime = endtime;
	}
	public int getStarttime() {
		return starttime;
	}
	public void setStarttime(int starttime) {
		this.starttime = starttime;
	}
	public int getEndtime() {
		return endtime;
	}
	public void setEndtime(int endtime) {
		this.endtime = endtime;
	}
	
//  return 양수 : 변화있음(오름차순: this - other, 내림차순: other - this)
	@Override
	public int compareTo(Conference other) {
		//종료시간을 기준으로 오름차순으로 정렬하고, 종료시간이 같을시 시작시간 기준으로 오름차순 정렬합니다.
		if(this.endtime == other.endtime) {		
			return this.starttime - other.starttime;
		}
		return this.endtime - other.endtime;
	}
	@Override
	public String toString() {
		return "toString test:"+starttime+" "+endtime+"\n";
	}
}

public class Main {
	
	public static int N;
	public static int starttime,endtime;
	public static int count=0, prev_endtime = 0;
	public static List<Conference> conferencelist = new ArrayList<>();
	
	public static void main(String[] args) {		
		Scanner sc = new Scanner(System.in);
		N=sc.nextInt();
		
		for(int i=0;i<N;i++) {
			starttime = sc.nextInt();
			endtime = sc.nextInt();
			conferencelist.add(new Conference(starttime, endtime));
		}
		Collections.sort(conferencelist);
//		System.out.println(conferencelist);
		for(int i=0;i<N;i++) {
			if(prev_endtime <= conferencelist.get(i).getStarttime()) {
				prev_endtime = conferencelist.get(i).getEndtime();
				count+=1;
			}
		}
		System.out.println(count);
	}
}

 

이번에는 배열로 익명 Comprator를 정렬해서 사용합니다.

package Main;
 
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.Comparator;
import java.util.StringTokenizer;
 
public class Main {
	static int N, M, S, P, A, B, X, L, R, C, n, k, m, l, K, D;
	static int answer = 0;
	static int[][] arr = new int[100001][2];
	public static void main(String[] args) throws IOException{
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());
		
		N = Integer.parseInt(st.nextToken());
		arr = new int[N][2];
		for(int i = 0; i<N; i++) {
			st = new StringTokenizer(br.readLine());
			arr[i][0] = Integer.parseInt(st.nextToken());
			arr[i][1] = Integer.parseInt(st.nextToken());
		}
		
		Arrays.sort(arr, 0, N, new Comparator<int[]>() {
			@Override
			public int compare(int[] a, int[] b) {
				if(a[1] != b[1]) {
					return Integer.compare(a[1], b[1]);
				}
				return Integer.compare(a[0], b[0]);
					
			}
		});

		int lastTime = -1;
		for(int i=0; i<N; i++) {
			if(lastTime <= arr[i][0]) {
				answer += 1;
				lastTime = arr[i][1];
			}
		}
		
		System.out.println(answer);
	}

}