[ 백준 / 파이썬 ] 골드 3 - 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)이 주어진다. 다음 N개의 줄에는 각 꽃이 피는 날짜와 지는 날짜가 주어진다. 하나의 날짜는 월과 일을 나타내는 두 숫자로 표현된다. 예를 들어서, 3 8 7 31은 꽃이 3월 8일에 피어서 7월 31일에 진다는 것을 나타낸다.

출력

첫째 줄에 선택한 꽃들의 최소 개수를 출력한다. 만약 두 조건을 만족하는 꽃들을 선택할 수 없다면 0을 출력한다.

예제

입력	출력
4 1 1 5 31 1 1 6 30 5 15 8 31 6 10 12 10	2

입력	출력
10 2 15 3 23 4 12 6 5 5 2 5 31 9 14 12 24 6 15 9 3 6 3 6 15 2 28 4 25 6 15 9 27 10 5 12 31 7 14 9 1	5

풀이

꽃이 피는 날 배열, 꽃이 지는 날 배열 두개를 선언하여 풀이했다.
우선, 입력으로 들어온 날짜들을 꽃이 피는 날을 기준으로 정렬한다.

3가지의 경우로 분류하여 문제를 풀었다.

배열의 길이가 0일 때는 시작일인 3월 1일로 비교하여, 꽃이 피는 날이 3월 1일 보다 작거나 같고, 꽃이 지는 날이 3월 1일보다 크면 배열에 각각 추가한다.

1. 배열의 길이가 1일 때는 가장 처음 심어진 꽃이 배열에 들어 있을 것이고, 만약 입력으로 받은 꽃이 3월 1일 전에 핀다면 배열에 들어있는 것과 비교하여 더 늦게 지는 꽃으로 첫번째 꽃을 설정한다.
   그렇지 않고 꽃이 피는 시기가 3월 1일 보다 크면 배열에 각각 추가한다.

2. 배열의 길이가 2 이상일 때는 가장 마지막에 심은 꽃과 비교한다.
   만약 가장 마지막에 심은 꽃이 지는 시기보다 심으려는 꽃의 지는 시기가 짧으면 패스, 또는 꽃이 피는 시기가 마지막에 심은 꽃이 지는 시기보다 늦으면 패스.

3. 위의 조건을 통과하면, 마지막에 심은 꽃의 지는 시기보다 심으려는 꽃의 지는 시기가 더 늦고, 전전에 심은 꽃이 지는 시기보다 심으려는 꽃의 피는 시기가 더 빠르다면 마지막에 심은 꽃을 현재 심으려는 꽃으로 교체한다.

만약 위의 경우가 아니라면 새로 꽃을 추가한다.

위 세가지 경우로 가장 적은 꽃으로 화단을 유지할 수 있다.

주의할 점은 화단을 유지 못하는 경우도 존재한다는 점을 생각해야 한다.

코드

from sys import stdin

input = stdin.readline

def early_start(A, B):
    if A[0] < B[0]:
        return True
    elif A[0] == B[0] and A[1] <= B[1]:
        return True

    return False

def early_end(A, B):
    if A[0] < B[0]:
        return True
    elif A[0] == B[0] and A[1] < B[1]:
        return True

    return False


def solution(N):
    answer = 0

    flowers = []

    for _ in range(N):
        sm, sd, em, ed = map(int, input().split())
        flowers.append([(sm, sd), (em, ed)])

    flowers.sort()

    for _ in flowers:
        print(_)

    start_arr = []
    end_arr = []

    possible = False

    for flower in flowers:
        S, E = flower
        if S == E:
            continue

        if not start_arr:
            if early_start(S, (3, 1)) and not early_end(E, (3, 1)):
                start_arr.append(S)
                end_arr.append(E)
                answer = 1
            continue

        if answer == 1:
            if early_start(S, (3, 1)) and not early_end(E, (3, 1)):
                if not early_end(E, end_arr[-1]):
                    start_arr[-1] = S
                    end_arr[-1] = E

            elif early_start(S, end_arr[-1]) and not early_end(E, end_arr[-1]):
                start_arr.append(S)
                end_arr.append(E)
                answer += 1
        else:
            if early_start(S, end_arr[-1]) and not early_end(E, end_arr[-1]):
                if early_start(S, end_arr[-2]):
                    start_arr[-1] = S
                    end_arr[-1] = E
                else:
                    start_arr.append(S)
                    end_arr.append(E)
                    answer += 1

        if not early_start(end_arr[-1], (11, 30)):
            possible = True
            break

    if not end_arr or not possible:
        answer = 0

    return answer


print(solution(int(input())))