[JUNGOL/Java] 1828. 냉장고

[JUNGOL/Java] 1828. 냉장고

JUNGOL

---

문제 해석

이 문제에서는 여러 화학 물질이 정해진 온도 범위 내에서 보관되어야 한다. 각 화학 물질은 최저 및 최고 보관 온도가 주어지며, 가능한 적은 수의 냉장고를 사용하여 모든 화학 물질을 안전하게 보관해야 한다. 각 냉장고는 하나의 온도 범위만을 가지며, 이 범위는 하나 이상의 화학 물질을 포함할 수 있다.

풀이 과정

제출된 Java 코드는 화학 물질을 최고 온도 기준으로 정렬한 뒤, 가장 낮은 최고 온도를 가진 화학 물질부터 시작하여 이 물질과 겹치는 모든 물질을 하나의 냉장고로 처리하는 그리디 알고리즘을 사용한다. 각 화학 물질은 Chemical 클래스로 표현되며, 이 클래스는 두 물질을 최고 온도에 따라 비교하는 Comparable 인터페이스를 구현한다.

 

• 데이터 입력 및 초기화: 화학 물질의 수와 각 물질의 최저/최고 온도를 입력받아 chemicalList에 저장한다.
• 화학 물질 정렬: chemicalList를 최고 온도 기준으로 오름차순 정렬한다.
• 냉장고 수 계산: 정렬된 리스트를 순회하면서 현재 선택된 화학 물질의 최고 온도가 다음 화학 물질의 최저 온도보다 높거나 같으면 같은 냉장고에 보관 가능하다. 그렇지 않은 경우 새 냉장고가 필요하다.

코드

package edu.ssafy.im.JUNGOL.Gold.G4.No1828;

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.ArrayList;
import java.util.Collections;
import java.util.List;
import java.util.StringTokenizer;

public class Main {
	public static void main(String[] args) throws NumberFormatException, IOException {
		new Main().io();
	}

	class Chemical implements Comparable<Chemical> {
		int low, high; // 최저, 최고 온도

		public Chemical(int low, int high) {
			super();
			this.low = low;
			this.high = high;
		}

		@Override
		public int compareTo(Chemical o) {
			return this.high - o.high; // 최고 온도를 기준으로 정렬
		}

	}

	private void io() throws NumberFormatException, IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
		StringBuilder sb = new StringBuilder();
		int n = Integer.parseInt(br.readLine());
		List<Chemical> chemicalList = new ArrayList<>();
		for (int i = 0; i < n; i++) {
			StringTokenizer st = new StringTokenizer(br.readLine());
			int low = Integer.parseInt(st.nextToken());
			int high = Integer.parseInt(st.nextToken());
			chemicalList.add(new Chemical(low, high));
		}
		Collections.sort(chemicalList); // 화학 물질 정렬
		
		int ans = 0;
		for (int j = 0; j < chemicalList.size(); j++) {
			Chemical c = chemicalList.get(j);
			ans++;
			
			for (int i = j; i < chemicalList.size(); i++) {
				if (c.high >= chemicalList.get(i).low) {
					chemicalList.remove(i); // 겹치는 화학 물질 제거
					i--;
				}
			}
			j--;
		}

		sb.append(ans);
		bw.write(sb.toString());
		bw.flush();
		bw.close();
	}
}

시간 복잡도 분석

이 코드는 각 화학 물질을 최고 온도 기준으로 정렬하는데 O(nlogn) 시간이 소요된다. 그리고 각 화학 물질을 처리하며 중첩된 화학 물질을 제거하는데 최악의 경우 O(n^2) 시간이 소요될 수 있다.

느낀점

이 문제를 통해 그리디 알고리즘의 효과적인 활용 방법을 배울 수 있었다. 화학 물질을 온도 기준으로 정렬하여 문제를 단순화하고, 중복되는 범위를 최소화하여 필요한 냉장고의 수를 줄일 수 있었다. 이러한 접근은 다양한 최적화 문제에서 유용하게 적용될 수 있다.