99클럽 코테 스터디 5일차 TIL <Baekjoon - [Gold III] 공주님의 정원 - 2457>

@developer/takealittle.time·2024년 11월 1일

99클럽 TIL 개발자취업 코딩테스트준비 항해99

99Club

목록 보기

5/9

[문제 링크]

성능 요약

메모리: 56484 KB, 시간: 1096 ms

분류

그리디 알고리즘, 정렬

문제 설명

오늘은 공주님이 태어난 경사스러운 날이다. 왕은 이 날을 기념하기 위해 늘 꽃이 피어있는 작은 정원을 만들기로 결정했다.

총 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일까지 매일 꽃이 한 가지 이상 피어 있도록 꽃들을 선택할 때, 선택한 꽃들의 최소 개수를 출력하는 프로그램을 작성하시오.

00. 발상

우선, 문제를 읽자마자 Greedy 알고리즘을 사용하는 강의실 배정 문제라는 것을 알았다.
그런데 이제 생각해줄 까다로운 조건들이 주렁주렁 달려있는.
날짜 정보를 그대로 (시작 월, 시작 일), (종료 월, 종료 일) 식으로 튜플로 묶을 수도 있겠으나,
정렬이나 뒤의 까다로운 조건 해결에 있어 이를 정수로 변환 해 주는 것이 좋겠다는 생각이 들었다.
강의실 배정 문제는 아래와 같이 해결한다.
1. 리스트(배열)에 시간 정보들을 할당한다.
2. 리스트에 필요에 따라 정렬 조건을 주어 정렬한다.
3. 정렬한 리스트에서 가장 조건에 부합하는 아이템을 꺼내면서 결과를 생성한다.
이 문제에서는 3월1일부터 11월30일까지 '꽃이 피어있는 기간'이 끊임없이 붙어있어야 하므로, 개화 시간을 기준으로 정렬한 다음, 꽃이 지는 날짜를 합산하며 일직선으로 꽃이 피어있는 기간이 붙는 이미지를 머릿속으로 그렸다.
이 때, 최대한 꽃이 느리게 지는 꽃들을 선택해야 한다.

01. 코드 작성

# 빠른 입력을 위해 sys.stdin 사용
import sys
input = sys.stdin.readline
# 꽃 개수 입력
N = int(input())
flowers = []
# 꽃 정보 입력
for _ in range(N):
    sm, sd, em, ed = map(int,input().split())
    # 날짜 정보를 3, 4자릿수 정수로 변환 해 리스트에 저장
    start = sm*100+sd
    end = em*100+ed
    flowers.append((start,end))
# 꽃 정보 정렬 (개화 시작 날짜 오름차순 정렬 후 지는 날짜 기준으로 오름차순 정렬)
flowers.sort(key = lambda x:(x[0],x[1]))
# 최종 합산 지는 날짜: 시작 할 때는 3월 1일
end_date = 301
# 결과 할당할 변수
result = 0
# flowers 배열에 값이 남아있는 동안 반복
while flowers:
    # 종료 조건: 최종 합산 날짜가 12월 01일 이상이거나, 중간에 이어지지 않는 경우
    if (end_date >= 1201 or flowers[0][0] > end_date):
        break

    tmp = -1
    for i in range(len(flowers)):
        # 개화 날짜가 최종 합산 지는 날짜보다 작은 꽃 중에서
        if flowers[0][0] <= end_date:
            # 가장 늦게 지는 꽃을 선택
            if tmp <= flowers[0][1]:
                tmp = flowers[0][1]
            # 조건 확인한 꽃은 리스트에서 제거
            flowers.remove(flowers[0])
        # 중간에 안이어지면 break
        else:
            break
    # 최종 합산 지는 날짜 업데이트
    end_date = tmp
    # 결괏값 +1
    result += 1
# 중간에 이어지지 않은 경우 0 출력
if end_date< 1201:
    print(0)
# 결과 출력
else:
    print(result)

02. 고민했던 부분과 해결

처음에는 날짜 정보를 소수로 변환 했었다.
하지만, 컴퓨터는 부동소수 변환과 친하지 않으므로 월 정보에 *100 연산을 통해 정수형으로 변환 해 주는 것이 낫겠다는 생각이 들었다.
함께 문제를 푼 친구는 힙을 사용해서 문제를 해결했다고 한다. while문 안에서 꽃을 선택하는 과정에 힙을 사용해 가장 느리게 지는 꽃을 결정하는데 사용했는데, 이 방법을 사용하면 우선 꽃 정보를 정렬할 때 개화 날짜만 기준으로 오름차순 정렬을 해주면 되므로 연산량이 줄겠다는 생각이 들었다.

시간 복잡도 면에서도 그렇고, 자료구조를 하나 활용하는 발상이 좋은 방법인 것 같아 이렇게도 문제를 한 번 해결 해 볼 생각이다.

03. 회고 및 느낀 점

사실, 오늘은 시간 안에 문제를 해결하지 못했다.
기본적인 강의실 배정 문제에 대한 내용은 머릿속에 있었으나, 이런저런 문제 조건들을 구현하다 삼천포로 빠졌다.
힙을 사용해 그리디 알고리즘을 해결하는 문제들이 꽤 있다고 한다. 이러한 문제들에 대해 개념적으로 정립해야 할 필요성을 느꼈다.

99클럽 TIL 개발자취업 코딩테스트준비 항해99