[JO] 1828번: 냉장고(Java)

1758 단어 그리디그리디

문제

JUNGOL 1828 


풀이

한 냉장고의 화학물질을 최대로 담아야 하므로 '그리디' 알고리즘 적용

화학물질의 최저 보관온도와 최고 보관 온도를 저장할 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);
	}
}

좋은 웹페이지 즐겨찾기