#15 [python] 2457번: 공주님의 정원

https://www.acmicpc.net/problem/2457

2457번: 공주님의 정원

 

✔️ 문제 분석

 

 첫째 줄에는 꽃들의 총 개수 N (1 ≤ N ≤ 100,000)이 주어진다. 다음 N개의 줄에는 각 꽃이 피는 날짜와 지는 날짜가 주어진다. 하나의 날짜는 월과 일을 나타내는 두 숫자로 표현된다. 예를 들어서, 3 8 7 31은 꽃이 3월 8일에 피어서 7월 31일에 진다는 것을 나타낸다. 첫째 줄에 선택한 꽃들의 최소 개수를 출력한다. 

 

ex) 3 8 7 31 : 3/18 ~ 7/31

 

💫 코드 분석

 

n = intput(int()) # n 값 받기

월에 100을 곱해 월/일 구별이 쉽게 만든다

모든 꽃이 없어질때 까지 반복

마지막 꽃 지는 날이 1201보다 크면 멈춤

마지막 꽃의 지는 날이 빨리 피는 꽃 보다 작으면 그사이 꽃이 없으므로 멈춤

꽃 확인하면 제거

최종적으로 선택한 꽃의 지는날을 바꿔주고 카운트

오름차순으로 정리 -> 같지 않으면 result 값 + 갱신

 

 

 

❗ 코드

import sys

n = int(sys.stdin.readline())
date = []

# 편의를 위해 100을 곱해 날짜 형식으로 바꿈
for _ in range(n):
    temp = list(map(int, sys.stdin.readline().split()))
    date.append([temp[0] * 100 + temp[1], temp[2] * 100 + temp[3]])

# 꽃이 피고 지는 날짜를 오름차순으로 정렬
date.sort(key=lambda x:(x[0], x[1]))
# 선택한 꽃의 개수
cnt = 0
# 제일 늦게 지는 꽃을 비교
end = 0
# 마지막 꽃의 지는 날
target = 301

# 모든 꽃이 없어질 때까지 반복하여 꽃을 비교한다.
while date:
    # 마지막 꽃의 지는날이 12월 1일 보다 크거나 같을 때와
    # 마지막 꽃의 지는날이 제일 빨리 피는 꽃보다 작으면 멈춘다.
    if target >= 1201 or target < date[0][0]:
        break

    # 꽃의 개수의 길이만큼 반복하여 구간별로 꽃을 비교한다.
    for _ in range(len(date)):
        # 마지막 꽃의 지는 날이 제일 빨리 피는 꽃보다 크거나 같으면 그 꽃의 지는 날을 확인한다.
        if target >= date[0][0]:
            # 그 꽃의 지는 날과 마지막으로 꽃의 지는 날을 비교한다.
            # 그 꽃의 지는 날이 더 크면 더 오래 꽃을 볼 수 있기때문에
            # 그 꽃의 지는 날을 마지막 꽃의 지는 날로 바꾼다.
            if end <= date[0][1]:
                end = date[0][1]

            # 꽃을 확인 하면 제거한다.
            date.remove(date[0])

        # 꽃의 지는 날이 제일 빨리 피는 꽃보다 작으면 멈춰준다.
        else:
            break

    # 최종적으로 선택한 꽃의 지는 날을 바꾼다.
    target = end
    # 꽃을 선택했으므로 카운트한다.
    cnt += 1

# 마지막 꽃의 지는 날이 12월 1일보다 작으면 11월 30일에는 피어있는 꽃이 없기때문에 0을 출력
if target < 1201:
    print(0)
else:
    print(cnt)

참고 : https://fre2-dom.tistory.com/51

 

[baekjoon] 백준 2457번(파이썬): 공주님의 정원