/* 문제설명 */
http://jungol.co.kr/bbs/board.php?bo_table=pbank&wr_id=1101&sca=30
아래의 풀이는 문제에 있는 테스트 케이스를 기준으로 설명하였다!
/* 풀이방법 */
일단 음식을 입력받아 arr에 모두 추가했다.
정렬을 하기위해 Food class는 Comparable을 상속받았고
최소온도 오름차순, 같다면 최고온도 오름차순으로 비교되도록 compareTo메소드를 구현했다.
그럼 다음과 같이 정렬되어 있게 된다.
그리고 스택을 하나 만들어서 (이때 스택의 한 요소는 냉장고를 의미한다)
첫번째 음식을 푸쉬한다.
그러면 해당 이제 저 냉장고(스택의 요소)는
-15 ~ 5도 사이의 온도를 유지하는 냉장고라는 의미이다.
이제 그다음 부터 arr에 있는 모든 음식을 순서대로 돌면서 냉장고와 값을 비교하면 된다.
배열에 있는 두번째 값을 스택에 있는 냉장고와 비교한다.
최저 온도가 더 높은 것으로 변경하고, 최고 온도 또한 더 낮은것으로 변경한다.
(그래야 두 음식에게 모두 적합한 온도가 되니까)
그래서 스택의 냉장고의 온도는 다음과 같이 변하게 된다.
만약 해당 범위를 넘어서는 음식이 들어온다면 그 음식은 현재 냉장고에 추가할 수 없으므로 새로운 요소를 스택에 추가 시키고 범위를 그 음식의 범위로 한다.
3번째 음식]
[4번째 음식]
그래서 스택의 사이즈인 2개의 냉장고가 필요하다.
/* 해답코드 */
package jungol;
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.Stack;
import java.util.StringTokenizer;
class Food implements Comparable<Food>{
public int low;
public int high;
public Food() {}
public Food(int low, int high) {
super();
this.low = low;
this.high = high;
}
@Override
public int compareTo(Food o) {
if(this.low == o.low)
return this.high - o.high;
return this.low - o.low;
}
}
public class j1828 {
public static void main(String[] args) throws NumberFormatException, IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st = null;
int N = Integer.parseInt(br.readLine());
Food[] arr = new Food[N];
Stack<Food> ref = new Stack<Food>();;
for(int i=0;i<N;i++) {
st = new StringTokenizer(br.readLine());
int low = Integer.parseInt(st.nextToken());
int high = Integer.parseInt(st.nextToken());
arr[i] =new Food(low,high);
}
Arrays.sort(arr);
ref.push(arr[0]);
for(int i=1;i<N;i++) {
boolean contain = false;
Food f = ref.pop();
if(f.low<=arr[i].low&&f.high>=arr[i].low) {
f.low = arr[i].low;
contain = true;
}
if(f.high>=arr[i].high&&f.low<=arr[i].high) {
f.high = arr[i].high;
contain = true;
}
ref.push(f);
if(!contain) {
ref.push(arr[i]);
}
}
System.out.println(ref.size());
}
}