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

문제

2457번: 공주님의 정원

- 총 N개의 꽃이 있는 데, 꽃은 모두 같은 해에 피어서 같은 해에 진다.

- 하나의 꽃은 피는 날과 지는 날이 정해져 있다.

- 예를 들어, 5월 8일 피어서 6월 13일 지는 꽃은 5월 8일부터 6월 12일까지는 꽃이 피어 있고, 6월 13일을 포함하여 이후로는 꽃을 볼 수 없다는 의미이다. (올해는 4, 6, 9, 11월은 30일까지 있고, 1, 3, 5, 7, 8, 10, 12월은 31일까지 있으며, 2월은 28일까지만 있다.)

- 이러한 N개의 꽃들 중에서 다음의 두 조건을 만족하는 꽃들을 선택하고 싶다.

1. 공주가 가장 좋아하는 계절인 3월 1일부터 11월 30일까지 매일 꽃이 한 가지 이상 피어 있도록 한다.
2. 정원이 넓지 않으므로 정원에 심는 꽃들의 수를 가능한 적게 한다. 

- N개의 꽃들 중에서 위의 두 조건을 만족하는, 즉 3월 1일부터 11월 30일까지 매일 꽃이 한 가지 이상 피어 있도록 꽃들을 선택할 때, 선택한 꽃들의 최소 개수를 구하는 문제이다.

- 꽃들의 총 개수 N (1 <=N <=100,000)이 주어진다.

- 각 꽃이 피는 날짜와 지는 날짜가 주어진다. 하나의 날짜는 월과 일을 나타내는 두 숫자로 표현된다.

- 예를 들어서, 3 8 7 31은 꽃이 3월 8일에 피어서 7월 31일에 진다는 것을 나타낸다. 

- 만약 두 조건을 만족하는 꽃들을 선택할 수 없다면 0을 출력한다.

알고리즘

- 꽃의 개수를 입력받는다.

- 꽃이 피는 날과 지는 날을 입력받는다. 이때, 편의를 위해 월에 해당하는 위치에 100을 곱하고 일에 해당하는 위치를 더해 날짜 형식으로 바꿔준다.

- 꽃을 비교할 때 피고 지는 순서대로 비교하기 위해 오름차순으로 정렬시킨다.

- 모든 꽃이 없어질 때까지 반복하여 꽃을 비교한다.

- 마지막 꽃의 지는 날이 12월 1일보다 크거나 같으면 그 후에 꽃은 비교하지 않아도 됨으로 멈춘다.

- 마지막 꽃의 지는 날이 제일 빨리 피는 꽃보다 작으면 그 사이에 꽃이 없으므로 멈춘다.

- 꽃의 개수의 길이만큼 반복하여 구간별로 꽃을 비교한다.

- 마지막 꽃의 지는 날이 제일 빨리 피는 꽃보다 크거나 같으면 그 꽃의 지는 날을 확인한다.

- 그 꽃의 지는 날과 마지막으로 꽃의 지는 날을 비교한다.

- 꽃을 확인하면 제거한다.

- 최종적으로 선택한 꽃의 지는 날을 바꿔준다.

- 꽃을 선택했으므로 카운트해준다.

- 최종적으로 선택한 꽃의 지는 날이 12월 1일보다 작으면 0을 출력하고 아니라면 카운트를 출력한다.

코드

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)

github

junjange/CodingTest