[백준] 2457번 : 공주님의 정원

2457번: 공주님의 정원

2457번: 공주님의 정원

🤔 문제분석

시작날짜, 끝나는 날짜 오름차순으로 정렬하여 순회하면서, 현재의 시작시간에서 다음의 가장 끝나는시간이 긴 날짜를 선택하여 문제를 해결 할 수 있다.

두개의 케이스로 문제를 해결하였는데 배열을 순회하는 방식과, 스택을 활용하는 방식 두가지로 문제를 해결하였다.

두가지 모두 현재의 시작 날짜에서 가장 늦게 끝나는 날짜를 선택하는 해야한다.

💻 코드

배열 순회 방식

import sys
input = sys.stdin.readline
START_CONDITION = 301
END_CONDITION = 1201

N = int(input())
flower = []

for i in range(N):
    s_month, s_day, e_month, e_day = map(int, input().split())
    flower.append((s_month*100 + s_day, e_month*100 + e_day))

flower.sort()
end_date = START_CONDITION
count = 0

while flower:
    if flower[0][0] > end_date or end_date >= END_CONDITION:
        break
    
    max_end_date = -1
    
    for _ in range(len(flower)):
        if (flower[0][0] <= end_date):
            if (max_end_date <= flower[0][1]):
                max_end_date = flower[0][1]

            flower.remove(flower[0])
        else:
            break
        
    end_date = max_end_date
    count += 1
    
if end_date < END_CONDITION:
    print(0)
else:
    print(count)

스택

import sys
input = sys.stdin.readline
START_CONDITION = 301
END_CONDITION = 1201

N = int(input())
flower = []

for i in range(N):
    s_month, s_day, e_month, e_day = map(int, input().split())
    flower.append((s_month*100 + s_day, e_month*100 + e_day))

flower.sort(key=lambda x:(-x[0], -x[1]))
end_date = START_CONDITION
count = 0

while flower:
    if flower[-1][0] > end_date or end_date >= END_CONDITION:
        break
    
    max_end_date = -1
    while flower and flower[-1][0] <= end_date:
        max_end_date = max(flower[-1][1], max_end_date)
        flower.pop()
    
    count += 1
    end_date = max_end_date

if end_date < END_CONDITION:
    print(0)
else:
    print(count)

🎯 피드백 및 개선사항

문제의 포인트는 현재의 시작 날짜에서 가장 늦게 끝나는 날짜를 선택하는 해야한다.