Greedy에서 상위/하위 호환 처리하기

문제

 

2457번: 공주님의 정원

 

---

 

재정의

3월 1일부터 11월 30일까지를 커버하는 최소의 꽃 개수 구하기.

1. x월 y일을 비교할 수 있게 정량화 하기.

2. 늦게 끝나는 순, 일찍 시작하는 순으로 정렬하기 (상위 호환 처리를 위해)

3. 정렬된 꽃을 11월 30일이 될 때 까지, 하나씩 집기.

 

월과 일을 정량화 하는 방법은 무수히 많지만,

두 가지 형태를 주로 사용한다.  날짜 비교하기 이 글에서 설명 된 방식 중, Day로 표현하는 방식을 사용 한다.

 

---

 

탐색의 중복

위의 재정의 대로 코드를 구현하면 다음과 같이 작성된다.

n = int(input())
blooming_end = date_to_sum(11, 30)
flowers = []

for _ in range(n):
    st_m, st_d, ed_m, ed_d = map(int, input().split())
    flowers.append((date_to_sum(st_m, st_d), date_to_sum(ed_m, ed_d)))

flowers.sort(key=lambda x: (-x[1], x[0]))
print(flowers)

flower_cnt = 0
now_day = date_to_sum(3, 1)

while now_day <= blooming_end:
    for flower in flowers:
        if flower[0] > now_day:
            continue

        flower_cnt += 1
        now_day = flower[1]
        break

print(flower_cnt)

n이 10,000 까지 범위를 가질 수 있다.

이 알고리즘은 O(n ** 2)으로 10 ** 8을 초과하기 때문에 시간 초과가 발생한다.

 

그렇다면 어디서 이를 줄일 수 있을까?

입출력을 보면 확인할 수 있다.

4
1 1 5 31
1 1 6 30
5 15 8 31
6 10 12 10
[(161, 344), (135, 243), (1, 181), (1, 151)]
2

 

탐색 과정은 다음과 같을 것이다.

 

(161, 344), (135, 243), !(1, 181)!
!(161, 344)!

 

상위 호환 처리를 하고자 정렬 조건을 (늦게 지는 순서, 일찍 피는 순서)로 하였다.

그래서 필 수 있는 꽃을 처음 만나면 최적의 꽃인게 보장이 되지만,

위에서 볼 수 있듯이, 이미 확인한 곳을 다시 확인하는 비효율적인 부분이 발생한다.

 

상위/하위 호환을 정렬로써 해결하지 않고, 다른 방식으로 제거해야 한다.

꽃을 입력 받을 때 마다, 상위/하위 호환을 체크할 수도 있다.

 

하지만, 우리는 어차피 꽃을 탐색해야 한다.

최적의 꽃을 고르기 위해서 한 번은 루프를 돌릴 것이다.

이 루프를 도는 과정에서 상위/하위 호환을 체크하면 효율적으로 확인할 수 있다.

 

---

 

탐색하면서 중복 제거하기

range에서 상위/하위 호환이란 간단하다.

시작일이 같거나 더 이른데, 종료일이 같거나 더 늦으면 상위/하위 호환이다.

 

이전에는 정렬 조건이  (늦게 지는 순서, 일찍 피는 순서) 였지만,

지금은 (일찍 피는 순서, 일찍 지는 순서)로 정렬 한다.

이래야만 상위/하위 호환이 연속되어 있으므로 처리를 할 수가 있다!

 

다음과 같이 진행할 수 있다.

1. 꽃을 뽑는다.
2. 현재 뽑은 꽃의 상위/하위 호환 꽃들을 처리하고 제거한다.

 

for _ in range(n):
    st_m, st_d, ed_m, ed_d = map(int, input().split())
    flowers.append((date_to_sum(st_m, st_d), date_to_sum(ed_m, ed_d)))

flowers.sort(key=lambda x: (x[0], x[1]))

flower_cnt = 0
bloom_ed = 0
last_bloom = blooming_st

while flowers:
    if last_bloom >= blooming_end\
            or last_bloom < flowers[0][0]:
        break

    for _ in range(len(flowers)):
        if last_bloom >= flowers[0][0]:
            if bloom_ed <=  flowers[0][1]:
                bloom_ed = flowers[0][1]
            
            flowers.remove(flowers[0])
        else:
            break

    last_bloom = bloom_ed
    flower_cnt += 1

if last_bloom < blooming_end:
    print(0)
else:
    print(flower_cnt)

 

전 처리하는 방식 뿐 아니라,

이처럼 탐색하면서 처리하는 방식도 가능하다!