[BOJ/Java] 2457. 공주님의 정원

[BOJ/Java] 2457. 공주님의 정원

2457번: 공주님의 정원

---

문제 해석

본 문제에서는 공주님의 정원을 3월 1일부터 11월 30일까지 꽃으로 가득 채우기 위해 필요한 최소한의 꽃 종류를 선택하는 방법을 찾는다. 각 꽃은 피는 시기와 지는 시기가 정해져 있으며, 이를 효과적으로 선택하여 연속적으로 꽃이 피어있게 해야 한다.

풀이 과정

제출된 코드는 꽃들의 생장 기간을 기반으로 그리디 알고리즘을 사용하여 문제를 해결한다. 모든 꽃들을 피는 시기를 기준으로 정렬하고, 각 단계에서 현재 날짜 이후로 가장 오래 지속되는 꽃을 선택한다. 이 과정을 11월 30일까지 반복하여 필요한 최소한의 꽃 수를 찾는다.

코드

package edu.ssafy.im.BOJ.Gold.G3.No2457;

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.*;

public class Main {
	private ArrayList<Flower> flowerList; // 꽃 리스트

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

	private int N; // 꽃의 종류 수
	private int ans = 0; // 필요한 최소 꽃의 수

	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();

		N = Integer.parseInt(br.readLine()); // 꽃의 종류 수 입력

		flowerList = new ArrayList<>();
		StringTokenizer st;
		for (int i = 0; i < N; i++) { // 각 꽃의 피고 지는 시기 입력
			st = new StringTokenizer(br.readLine());
			int sm = Integer.parseInt(st.nextToken());
			int sd = Integer.parseInt(st.nextToken());
			int em = Integer.parseInt(st.nextToken());
			int ed = Integer.parseInt(st.nextToken());

			flowerList.add(new Flower(sm * 100 + sd, em * 100 + ed)); // 날짜를 숫자로 변환하여 저장
		}
		sol();
		sb.append(ans);
		bw.write(sb.toString());
		bw.flush();
		bw.close();
	}

	private void sol() {
		Collections.sort(flowerList); // 꽃 리스트를 피는 시기 기준으로 정렬

		int start = 301; // 시작 일자 (3월 1일)
		int end = 1201; // 종료 일자 (12월 1일)
		int now = 0; // 현재 커버 가능한 최대 일자
		int idx = 0; // 현재 확인 중인 꽃의 인덱스

		while(start < end) {
			boolean flag = false;

			for (int i = idx; i < N; i++) {
				if (flowerList.get(i).s > start) break; // 시작 일자 이후에 피는 꽃이면 중단
				if (flowerList.get(i).e > now) { // 현재 날짜를 넘어서는 꽃이 있으면 선택
					flag = true;
					now = flowerList.get(i).e; // 꽃의 지는 시기를 업데이트
					idx = i + 1; // 다음 꽃 확인
				}
			}

			if(flag) {
				start = now; // 다음 시작 일자 업데이트
				ans++; // 선택된 꽃 수 증가
			} else {
				break; // 더 이상 진행할 수 없는 경우
			}
		}

		if(now < end) ans = 0; // 11월 30일을 커버하지 못하는 경우
	}

	class Flower implements Comparable<Flower> { // 꽃 클래스
		int s, e; // 피는 날짜와 지는 날짜

		public Flower(int s, int e) {
			this.s = s;
			this.e = e;
		}

		@Override
		public int compareTo(Flower o) { // 정렬 기준 설정
			if(this.s < o.s) return -1;
			else if(this.s == o.s) {
				if(this.e > o.e) return -1; // 같은 날짜에 피는 경우 지는 날짜가 늦은 순으로 정렬
				else if(this.e == o.e) return 0;
				else return 1;
			} else return 1;
		}
	}
}

시간 복잡도 분석

본 코드는 꽃 리스트를 정렬하는 데 𝑂(𝑁log⁡𝑁)의 시간이 소요되며, 각 꽃에 대한 확인은 최악의 경우 𝑂(𝑁)이 될 수 있다. 전체적인 시간 복잡도는 𝑂(𝑁log⁡𝑁+𝑁)으로, 문제 해결에 충분히 효율적이다.

느낀점

본 문제를 통해 정렬과 그리디 알고리즘을 적절히 조합하여 문제를 해결하는 방법을 배웠다. 각 상황에서 최적의 선택을 하는 방식으로 문제를 접근하는 것은 다양한 문제에 유용하게 적용될 수 있다.