[알고리즘] 그리디

그리디는 정해진 방법이 없다.

해당 문제가 그리디라는 것을 눈치챘다면 순간의 센스가 8할이라고 한다.

그렇다면 패스..하려다가 일단 가장 대표적인 그리디 문제의 유형 하나쯤은 마스터해놓는 것도 나쁘진 않겠다 싶어 정리를 한다.

 

가장 유명한 예제는 바로 회의실 예약하는 문제이다. 그림을 그려서 푸는게 말로 100마디 하는것보다 훨씬 이해가 잘되니 글은 그림으로 해도 안될때 읽기 바란다.

 

회의실은 하나인데, 회의는 10개이다. 어느 회의를 회의실에 예약해야 가장 많은 회의를 진행시킬 수 있을까?

구현 시 재밌던 점은 Meeting 클래스를 하나 더 만들고 Comparable을 상속하여 compareTo메소드를 오버라이드 한것이다.

이는 회의실의 종료시간을 기준으로 오름차순 정렬을 해야 하는데, 사용자 정의 클래스를 정렬 할때의 기준을 잡아주기 위한 것이다. 만약 종료시간이 같다면 시작시간이 빠른것을 앞에 놓아야 한다. 그래야 직전회의의 종료시간과 현재회의의 시작시간을 비교할 때 하나라도 더 추가할 수 있기 때문이다.

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;
import java.util.Scanner;
/**
 입력:
 10
 1 4 1 6 6 10 5 7 3 8 5 9 3 5 8 11 2 13 12 14
 */
public class MeetingRoomGreedyTest {

	static class Meeting implements Comparable<Meeting>{
		
		int start,end;

		public Meeting(int start, int end) {
			super();
			this.start = start;
			this.end = end;
		}

		@Override
		public int compareTo(Meeting o) {
			return this.end != o.end? this.end - o.end : this.start - o.start;
		}
		
	}
	
	public static void main(String[] args) {

		Scanner sc = new Scanner(System.in);
		int count = sc.nextInt(); // 회의수
		
		Meeting[] meetings = new Meeting[count];
		for (int i = 0; i < count; i++) {
			meetings[i] = new Meeting(sc.nextInt(), sc.nextInt());
		}
		
		List<Meeting> result = getSchedule(meetings);
		
		StringBuilder sb = new StringBuilder();
		sb.append(result.size()).append("\n");
		
		for (Meeting meeting : result) {
			sb.append(meeting.start).append(" ").append(meeting.end).append("\n");
		}
		
		System.out.println(sb.toString());
	}
	
	public static List<Meeting> getSchedule(Meeting[] meetings){
		
		ArrayList<Meeting> result = new ArrayList<Meeting>();
		// 회의 목록을 종료시간 기준으로 오름차순, 종료시간이 같다면 시작시간 기준으로 오름차순 정렬
		Arrays.sort(meetings); 
		result.add(meetings[0]); // 첫회의 추가(종료시간이 가장 빠른 회의)
		 
		for (int i = 1, size = meetings.length; i < size; i++) {
			// 직전회의의 종료시간과 현재회의의 시작시간 비교
			if(result.get(result.size()-1).end <= meetings[i].start) {
				result.add(meetings[i]);
			}
		}
		return result;
	}
}

 

 

비슷한 유형의 문제는 바로 냉장고 개수 맞추기이다. 

http://www.jungol.co.kr/bbs/board.php?bo_table=pbank&wr_id=1101&sca=99&sfl=wr_hit&stx=1828 

JUNGOL

얘도 마찬가지로 온도의 최고값을 기준으로 정렬하기 위해 Temperatures클래스를 만들고 Comaprable을 상속했다. 하나씩 이동하면서 내가 세운 기준과 비교해주면 된다.

package ws0215;

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

public class JUNGOL1828_냉장고 {

	//정렬을 위해 Comparable 상속
	private static class Temperatures implements Comparable<Temperatures> {
		int min;
		int max;

		public Temperatures(int min, int max) {
			this.min = min;
			this.max = max;
		}

		@Override
		public int compareTo(Temperatures o) {
			int diff = this.max - o.max;
			return diff != 0 ? diff : this.min - o.min;// 최댓값으로 오름차순정렬, 같으면 최솟값으로 오름차순정렬
		}
	}

	public static void main(String[] args) throws Exception {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		int N = Integer.parseInt(br.readLine());
		Temperatures[] temps = new Temperatures[N];


		int ans = 1;
		for (int i = 0; i < N; i++) {
			StringTokenizer st = new StringTokenizer(br.readLine());
			temps[i] = new Temperatures(Integer.parseInt(st.nextToken()), Integer.parseInt(st.nextToken()));
		}
		Arrays.sort(temps);
		int maxNum = temps[0].max;

		//기존의 최댓값보다 다음온도의 최솟값이 더 크면 기존냉장고로 커버를 못하니까 하나 더 증가
		for(int i=0; i<N-1; i++) {
			if(maxNum < temps[i+1].min) {
				ans++;
				maxNum = temps[i+1].max;
			}
		}
		System.out.println(ans);
	}

}