[JO] 1828번: 냉장고(Java)
문제
풀이
한 냉장고의 화학물질을 최대로 담아야 하므로 '그리디' 알고리즘 적용
화학물질의 최저 보관온도와 최고 보관 온도를 저장할 Material 클래스 선언
Material클래스에 Comparable를 implement하여 max값에 따라 오름차순으로 정렬될 수 있도록 함.
오름차순 정렬 후, Max를 첫번째 원소의 max값으로 저장.
mat[i]의 min 값이 현재 max값보다 클 경우 같이 저장할 수 없으므로 cnt + 1 한 후,
max값을 해당 원소의 max값으로 재설정
(이미 max값에 따른 오름차순 정렬을 진행 하였으므로 다음 원소의 max값이 이전 max값보다 작을 수 없음)
코드
import java.io.*;
import java.util.*;
public class Main {
static class Material implements Comparable<Material>{
int min, max;
public Material(int min, int max) {
super();
this.min = min;
this.max = max;
}
@Override
public int compareTo(Material o) {
int val = this.max - o.max;
if(val != 0) return val;
return 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());
Material[] mat = new Material[n];
for(int i =0 ; i< n ; i++) {
StringTokenizer st = new StringTokenizer(br.readLine()," ");
mat[i] = new Material(Integer.parseInt(st.nextToken()), Integer.parseInt(st.nextToken()));
}
Arrays.sort(mat);
int max = 0;
int cnt = 1;
for(int i =1 ; i < mat.length ; i++) {
if(max<mat[i].min) {
cnt++;
max = mat[i].max;
}
}
System.out.println(cnt);
}
}
Author And Source
이 문제에 관하여([JO] 1828번: 냉장고(Java)), 우리는 이곳에서 더 많은 자료를 발견하고 링크를 클릭하여 보았다 https://velog.io/@dot2__/JO-1828번-냉장고Java저자 귀속: 원작자 정보가 원작자 URL에 포함되어 있으며 저작권은 원작자 소유입니다.
우수한 개발자 콘텐츠 발견에 전념 (Collection and Share based on the CC Protocol.)