[백준 2457] 공주님의 정원

문제 출처

사용 언어: Java

1. 구상

알고리즘 및 코드 참고

• 꽃의 피는 날과 지는 날을 저장하는 Flower 클래스를 생성
  → 피는 날이 적은 순으로, 늦게 지는 순으로 정렬할 수 있도록 정렬 기준 오버라이딩하기
  
  
• 월, 일은 MMDD로 변환하여 저장하기
  (ex. 3월 1일 → 301, 12월 1일 → 1201)
  
  
  
• 꽃이 피는 날짜는 3월 1일보다 점이어야 하며 꽃이 지는 날짜는 12월 1일 이상 이어야 한다.
  그 중에서도 오래 피어 있는 꽃을 선택
  
  

2. 구현

import java.io.IOException;
import java.util.Arrays;
import java.util.NoSuchElementException;
import java.util.Scanner;

public class sol_2457 {

	public static void main(String[] args) throws NoSuchElementException, IOException {
		Scanner s = new Scanner(System.in);		
		
		int num = s.nextInt();
		
		Flower[] flower = new Flower[num];
		
		for (int i = 0; i < num; i++) {
			/*날짜를 월, 일로 구분하지 않고 100을 곱하여 
            MMDD로 표현 (ex. 3월 1일 -> 301)*/
			int startMonth = s.nextInt();	
			int startDay = s.nextInt();
			int endMonth = s.nextInt();
			int endDay = s.nextInt();
			
			int start = startMonth * 100 + startDay;
			int end = endMonth * 100 + endDay;
			
			flower[i] = new Flower(start, end);
		}
		
		//Flower 객체에서 정의한 기준으로 정렬
		Arrays.parallelSort(flower);
		
		/*11월 30일까지 꽃이 피어 있어야 하므로 
        12월 1일에 꽃이 지는 기준일로 설정*/
		int close = 1201;
		int open  = 301;		
		int cnt = 0; //선택한 꽃들의 최소 개수를 세는 변수
		int max = 0;
		int idx = 0; //탐색하는 꽃의 위치 변수
		
		//종료일이 12월 1일보다 적은 경우에만 반복
		while (open < close) {
			boolean isFinded = false; //해당 꽃을 탐색했는지
			
			//꽃들 중 시작일이 기준에 부합하고 늦게 지는 꽃을 선택
			for (int i = idx; i < num; i++) {
				//시작일이 기준보다 빠르면 X (조건에 부합하지 않음)
				if(flower[i].start > open)
					break;
				
				/*종료일이 긴 꽃을 선택하는 게 
                최소한의 꽃을 선택할 수 있으므로 해당꽃을 선택*/
				if (max < flower[i].end) {
					isFinded = true;
					max = flower[i].end;
					idx = i + 1;
				}
			}
			
            //선택했다면 피는 날짜를 조정하고 선택한 꽃 수를 증가
			if (isFinded) {
				open = max;
				cnt++;
			}
			
			else
				break;
			
			
		}
	
	
		//모든 12월 1일 전에 지는 꽃들이면 선택을 하지 않으므로 0
		if (max < close)
			System.out.println(0);
		
		else
			System.out.println(cnt);
	
	
	
} 
}