[정보올림피아드 알고리즘] 정올 1828번 냉장고 자바(Java)

@notepad_jj2

츄르사려고 코딩하는 코집사입니다.

---

1. [정보올림피아드 알고리즘] 정올 1828번 냉장고 자바(Java)

1) 문제번호 : 1828번

 

2) 문제 출처

www.jungol.co.kr/bbs/board.php?bo_table=pbank&wr_id=1101&sca=99&sfl=wr_subject&stx=%EB%83%89%EC%9E%A5%EA%B3%A0

JUNGOL

 

2. 문제

N개의 화학 물질 C1, C2, …, Cn이 있다.

이들 각각은 보관되어야 할 온도가 각기 다른데, 각 Ci마다 최저 보관 온도 xi와 최고 보관 온도 yi가 정해져 있다. 

즉 Ci는 온도 xi이상, yi이하의 온도에서 보관되어야만 안전하다.

 

이 화학 물질들을 모두 보관하기 위해서는 여러 대의 냉장고가 필요한데 가능하면 적은 수의 냉장고를 사용하고 싶다. 

이를 해결하는 프로그램을 작성하시오.

 

3. 제약사항

- 

4. 입력

첫줄에 화학물질의 수 N이 입력된다. N의 범위는 1이상 100 이하이다.

두 번째 줄부터 N+1줄까지 최저보관온도와 최고보관온도가 입력된다. 

보관온도는 -270° ~ 10000°이며, 각 냉장고는 임의의 정해진 온도를 일정하게 유지할 수 있고, 냉장고는 아주 크다고 가정한다.

 

5. 출력

첫줄에 최소로 필요한 냉장고의 대수를 출력한다.

 

6. 풀이

- 맨 처음에 화학물질의 최저온도에서 냉장고 1개가 필요하므로, 처음 냉장고의 count는 1로 설정

- N행 2열의 2차원 배열을 선언하여 최저온도는 0열, 최고온도는 1열에 저장

- 최고온도를 오름차순으로 정렬

- i행의 최저온도와 최고 온도보다 max_Degree가 크면 max_Degree는 i,1값으로 설정

- i행의 최저온도가 max_Degree보다 크면 max_Degree는 i행의 최고온도가 되고 count 증가

 

7. 소스 코드

import java.util.*;

public class Solution {
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		int N = sc.nextInt(); //화학물질의 수
		int[][] arr = new int[N][2];
		
		int count = 1; // 냉장고의 개수 -> 최저에서 1개 기본적으로 들고감
		
		//최저온도는 arr[i][0], 최고온도는 arr[i][1]에 저장
		for(int i=0;i<N;i++) {
			arr[i][0] = sc.nextInt();
			arr[i][1] = sc.nextInt();
		}
		
		//최고온도를 오름차순으로 정렬
		Arrays.sort(arr, new Comparator<int[]>() {
			@Override
			public int compare(int[] o1, int[] o2) {
				return Integer.compare(o1[1], o2[1]);
			}
		});
		
		//맨 처음에 들어온 화학물질의 최고온도를 max_Degree로 설정
		int max_Degree = arr[0][1];
		
		//i행의 최저온도와 최고 온도보다 max_Degree가 크면 max_Degree는 i,1값이 된다.
		for(int i=0;i<N;i++) {
			if(arr[i][0]<=max_Degree) {
				if(arr[i][1]<max_Degree) {
					max_Degree = arr[i][1];
				}
				continue;
			}
			
			//i행의 최저온도가 max_Degree보다 크면 max_Degree는 i행의 최고온도가 되고 count 증가
			else {
				max_Degree = arr[i][1];
				count++;
			}
		}
		System.out.println(count);
	}
}

import java.util.*;

public class Solution {
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		int N = sc.nextInt(); // 화학물질 개수
		int[][] arr = new int [N][2];
		
		for(int i=0;i<N;i++) {
			arr[i][0] = sc.nextInt(); //최저온도
			arr[i][1] = sc.nextInt(); //최고온도
		}
		
		//최대온도로 오름차순 정렬 후
		Arrays.sort(arr, new Comparator<int[]>() {
			@Override
			public int compare(int[] o1, int[] o2) {
				return Integer.compare(o1[1], o2[1]);
			}
		});
		
		//첫번째 냉장고를 첫번째 재료의 최대온도로 셋팅한다.
		int count = 1;
		int max = arr[0][1];
		
		//두번째 재료부터 검사해가면서
		for(int i=1;i<N;i++) {
			//마지막 냉장고의 온도보다 높은 최저온도의 재료를 만나면
			if(max < arr[i][0]) {
				//그 재료의 최대온도로 맞춘 냉장고로 추가
				max = arr[i][1];
				count++;
			}
		}
		System.out.println(count);
	}
}

---