[그리디] 백준 2457번 공주님의 정원 Python 풀이

문제 요약

총 N개의 꽃이 있다. 모든 꽃은 같은 해에 피고 같은 해에 진다. 각 꽃은 피는 날과 지는 날이 정해져 있어 피는 기간이 아닐 경우, 꽃을 볼 수 없다. 이러한 꽃들 중, 다음 조건을 만족하는 꽃을 선택한다.

1. 3월 1일부터 11월 30일까지 매일 꽃이 한 가지 이상 피어 있음
2. 꽃은 최소 개수

백준 2457번 문제 바로가기

입력

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

출력

여러분은 T초를 위한 최소버튼 조작의 A B C 횟수를 첫 줄에 차례대로 출력해야 한다. 각각의 횟수 사이에는 빈 칸을 둔다. 해당 버튼을 누르지 않는 경우에는 숫자 0을 출력해야한다. 만일 제시된 3개의 버튼으로 T초를 맞출 수 없으면 음수 -1을 첫 줄에 출력해야 한다.

입출력 예시

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

작성 코드

오답

import sys
N = int(input())
days = []
for i in range(N):
    days += [list(map(int, sys.stdin.readline().split()))]


def flower():
    count = 0
    startDay = [3, 1]
    endDay = [3, 1]
    checkDay = []
    for k in range(N):
        for j in range(N):
            if ((days[j][0] < startDay[0]) or (days[j][0] == startDay[0] and days[j][1] <= startDay[1])) and \
                    ((days[j][2] > endDay[0]) or (days[j][2] == endDay[0] and days[j][3] >= endDay[1])):
                checkDay = days[j]
                endDay = [days[j][2], days[j][3]]
        if [checkDay[2], checkDay[3]] == [startDay[0], startDay[1]]:
            return count
        elif checkDay:
            count += 1
        elif count == 0:
            return 0
        startDay = [checkDay[2], checkDay[3]]
        checkDay = []
    return count


print(flower())

시작일이 11월 30일을 넘어갔을 때를 처리하지 않았다. 시간초과가 나왔지만, 시간이 초과되지 않았어도 틀렸을 문제

피드백

정렬 후 값을 찾을지 패턴에 따라 일일이 찾을지 고민하다가 일단 정렬하지 않고 구현했는데, 시간 초과로 틀렸다. 물론 패턴을 제대로 찾아내지 못해서 시간 초과가 걸리지 않았더라도 틀렸을 코드이다.

 

내가 찾은 패턴

• 필수 기준 : (시작일 3월 1일 이전 & 종료일 3월 1일 이후) or 시작일 11월 30일 이전
• 시작일 : 이전 종료일보다 이른 날짜 ((동일한 달 & 이른 날짜) or 이른 달)
• 종료일 : 시작일 기준이 충족하는 값 중에서 가장 늦은 날짜 ((동일한 달 & 늦은 날짜) or 늦은 달)

다른 블로그의 코드를 참고하여 공부했다.

 

참고 블로그 1 백병원 (Python)

• 꽃을 찾아내면 count를 +1 하고 count를 출력해내는 것보다 찾아낸 꽃의 배열을 만드는 방법이 더 빠름
• 입력받는 날짜들을 start_month, start_day, end_month, end_day로 전부 나누어 저장
  (더 헷갈리지 않고 작성할 수 있을 것 같다.)

[Python 3] BJ 2457-공주님의 정원

참고 블로그 2 꾸준함 (C++)

• month에 100을 곱하면 mmdd 형식이 되어 계산하기 편리
• 날짜 정렬하여 계산

백준 2457번 공주님의 정원

깨달은 것

• 대부분 month에 100을 곱한 뒤, 정렬하여 계산하는 것 같다.
• 좀 더 보기 쉽게, 좀 더 효율적으로 작성하도록 하자.
  (startDay, endDay로만 나눈게 코드 풀면서 헷갈렸었는데 그대로 뒀던 것, 정렬을 사용하면 더 효율적일 것 같았는데 없이 풀었던 것. 반성)