[Unsolved][JAVA] 정올 1628 냉장고

http://www.jungol.co.kr/bbs/board.php?bo_table=pbank&code=1828&sca=3050 

JUNGOL

 

1. 서론

 

나에게 그리디 알고리즘이 뭔지 제대로 알게 해 준 문제다. 

그리디 알고리즘 문제는 보통 범위가 나오고, 그 범위를 문제에서 준 기준에 따라 정렬을 하고, 그 계산의 최대나 최소를 구하는 문제 유형이다. 그렇지만 문제가 다 똑같지는 않다. 범위를 어떤 기준으로 정렬할 것인가, 그리고 주어진 문제에 따라 적절하게 계산을 구현할 수 있는가. 이 두 개가 그리디 알고리즘의 키 포인트이다.

 

2. 문제 풀이

 

어떤 화학물질의 최저, 최고 보관 가능온도가 주어진다. 이때 이 온도를 충족시켜서 보관할 수 있는 냉장고의 최소 개수를 구하는 문제이다.

 

문제 자체는 되게 심플한데 딱히 풀이법이 딱 떠오르지 않았다. 그냥 사실 처음에는 문제 자체도 이해가 잘 안갔다. 최소 ~ 최대 범위 값 안에 다른 화학물질을 포함시키면 온도가 어긋나는 게 아닌가 싶었는데 임의로 한 온도를 정할 수 있다고 가정한다고 쓰여있는 걸 봐서는 범위 안의 한 온도만 겹친다면 가능하다고 가정하는 것 같다.

 

근데 그래도 딱히 뾰족한 방법이 떠오르지 않았다. 그리디니까 일단 최저온도 순, 최고온도 순으로 각자 정렬해보고 어떻게 계산하는게 좋을까 보다가 감이 안 와서 결국엔 인터넷에 검색을 했다.

 

https://sohee-dev.tistory.com/25

[정올] 1828: 냉장고 (Java) / 그리디

 

너무 친절하게 그림까지 넣어서 설명이 되어있다. 

 

즉, 최고 온도 순으로 정렬후에 제일 앞의 값을 기준점으로 삼아서 그 기준점을 기준으로 다음 값과 최저온도를 비교하고 그 안에 포함되면 총물건의 수에서 하나씩 지워가는 형태로 냉장고의 수를 구하는 방법이다.

 

그래서 이 문제에서 비슷한 문제가 회의실배정이라길래 내가 전에 풀었던 회의실 배정 코드를 참고했다.

 

https://coding-log.tistory.com/4

[C++] 백준 1931 회의실배정 (+ JAVA 코드 추가)

 

처음에는 논리가 거의 똑같아 보이길래 그냥 이 문제에 맞춰서 입출력만 고치고 똑같이 돌려봤는데 점수가 10점이 나왔다.(그럼 그렇지)

근데 이 문제와 그 문제는 계산 부분 빼고는 코드가 거의 똑같더라는... (심지어 계산 부분도 거의 비슷)

 

3. 코드 설명

 

import java.awt.Point;
import java.io.*;
import java.util.*;

public class Main {
	
	public static void main(String[] args) throws IOException {
		Scanner s = new Scanner(System.in);
		
		int n = s.nextInt();
		
		List<Point> a = new ArrayList<Point>();
		for (int i = 0; i < n; i++) {
			int x = s.nextInt(), y = s.nextInt(); //최저, 최고
			Point p = new Point(x, y);
			a.add(p);
		}
		
		Collections.sort(a, new Comparator<Point>() {
			@Override
			public int compare(Point o1, Point o2) { //최고온도 순으로 정렬
					return o1.y - o2.y;
			}
		});
		
		int tmp = a.get(0).y, cnt = n; //최대를 물질 수만큼 저장
		for (int i = 1; i < n; i++)
			if (tmp >= a.get(i).x) //물질이 범위 안에서 커버되면 한 개의 냉장고에 통합
				cnt--;
			else
				tmp = a.get(i).y; //다른 범위로 옮김
		
		System.out.println(cnt);
	}	
}

 

 

최고온도를 기준으로 정렬한다.(오름차순)

최대 온도가 최소 온도를 커버하면 cnt 해준다.(하나의 냉장고에 넣는 개수 cnt)

그것과 다른 경우가 나오면 비교 기준인 최고온도 값을 다음 순서의 값으로 바꿔준다.