[백준 2457번] 공주님의 정원 문제 풀이 (with Python)

 

 

< 문제 >

 

 

 

 

 

< 입출력 >

 

 

 

 

 

< 풀이 >

 

날짜 비교를 편하게 하기 위해 날짜를 아래와 같이 정수로 나타내 주었다.

calendar = [31, 28, 31, 30, 31, 30, 31, 31, 30, 31, 30, 31]  # 각 달의 마지막 날짜
def calculateDate(x, y):
    date = 0
    for i in range(x-1):
        date += calendar[i]
    date += y
    return date

 

 

 

각 꽃이 피고 지는 시기를 정수로 계산해 배열에 넣어 준후, 배열을 피는 시기로 먼저 오름차순 배열한 후, 지는 시기로 오름 차순 배열했다.

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

 

 

 

TRY 1 - 이 전의 지는 시기보다 다음 꽃이 피는 시기가 작거나 같으면서, 이전의 지는 시기보다 다음 꽃이 지는 시기가 가능한 경우 중 가장 큰 값을 result에 넣는다.  

while now_endDt < endDt:        # 11월 30일보다 크면 끝남
    n = start_index             # result 에 있는 이전 인덱스 값
    t = now_endDt
    for i in range(start_index + 1, len(blossom)):
        if blossom[i][0] <= now_endDt:
            if blossom[i][1] > t:   # 앞의 끝나는 값이 더 큰 경우
                start_index = i
                t = blossom[i][1]
        else:
            break
    if start_index == n:       # 조건에 만족하는 값이 없을 때
        print(0)
        exit(0)
    if start_index == len(blossom) - 1 and t <= endDt:  # 끝까지 돌았으나 11월 30일 보다 작은 경우
        print(0)
        exit(0)
    result.append([blossom[start_index][0], blossom[start_index][1]])
    now_endDt = blossom[start_index][1]

print(len(result))

→ 16퍼센트에서 틀렸다고 뜬다.

 

 

 

TRY 2 -

from collections import deque

N = int(input())
blossom = []
calendar = [31, 28, 31, 30, 31, 30, 31, 31, 30, 31, 30, 31]  # 각 달의 마지막 날짜
def calculateDate(x, y):
    date = 0
    for i in range(x-1):
        date += calendar[i]
    date += y
    return date

startDt = calculateDate(3, 1)
endDt = calculateDate(11, 30)

queue = deque()
for i in range(N):
    arr = list(map(int, input().split()))
    blossom.append([calculateDate(arr[0], arr[1]), calculateDate(arr[2], arr[3])])

blossom.sort(key=lambda x: (x[0], x[1]))    # 시작 시간, 끝나는 시간으로 오름차순 정렬
cnt = 0
now_endDt = startDt   # 꽃이 추가될 때 갱신
end = 0     # 제일 늦게 지는 꽃

while blossom:

    if now_endDt >= endDt or now_endDt < blossom[0][0]:
        break
    for _ in range(len(blossom)):
        if now_endDt >= blossom[0][0]:
            if end <= blossom[0][1]:
                end = blossom[0][1]

            blossom.remove(blossom[0])
        else:
            break
    now_endDt = end
    cnt+=1

if now_endDt <= endDt:
    print(0)
else:
    print(cnt)

 

 

 

 

< 코드 >

TRY 1 - 실패

from collections import deque

N = int(input())
blossom = []
calendar = [31, 28, 31, 30, 31, 30, 31, 31, 30, 31, 30, 31]  # 각 달의 마지막 날짜
def calculateDate(x, y):
    date = 0
    for i in range(x-1):
        date += calendar[i]
    date += y
    return date

startDt = calculateDate(3, 1)
endDt = calculateDate(11, 30)

queue = deque()
for i in range(N):
    arr = list(map(int, input().split()))
    blossom.append([calculateDate(arr[0], arr[1]), calculateDate(arr[2], arr[3])])

blossom.sort(key=lambda x: (x[0], x[1]))    # 시작 시간, 끝나는 시간으로 오름차순 정렬
now_endDt = startDt       # 꽃이 추가될 때 갱신
result = []
start_index = -1

while now_endDt < endDt:        # 11월 30일보다 크면 끝남
    n = start_index             # result 에 있는 이전 인덱스 값
    t = now_endDt
    for i in range(start_index + 1, len(blossom)):
        if blossom[i][0] <= now_endDt:
            if blossom[i][1] > t:   # 앞의 끝나는 값이 더 큰 경우
                start_index = i
                t = blossom[i][1]
        else:
            break
    if start_index == n:       # 조건에 만족하는 값이 없을 때
        print(0)
        exit(0)
    if start_index == len(blossom) - 1 and t <= endDt:  # 끝까지 돌았으나 11월 30일 보다 작은 경우
        print(0)
        exit(0)
    result.append([blossom[start_index][0], blossom[start_index][1]])
    now_endDt = blossom[start_index][1]

print(len(result))

 

 

 

TRY 2 - 실패

from collections import deque

N = int(input())
blossom = []
calendar = [31, 28, 31, 30, 31, 30, 31, 31, 30, 31, 30, 31]  # 각 달의 마지막 날짜
def calculateDate(x, y):
    date = 0
    for i in range(x-1):
        date += calendar[i]
    date += y
    return date

startDt = calculateDate(3, 1)
endDt = calculateDate(11, 30)

queue = deque()
for i in range(N):
    arr = list(map(int, input().split()))
    blossom.append([calculateDate(arr[0], arr[1]), calculateDate(arr[2], arr[3])])

blossom.sort(key=lambda x: (x[0], x[1]))    # 시작 시간, 끝나는 시간으로 오름차순 정렬
cnt = 0
now_endDt = startDt   # 꽃이 추가될 때 갱신
end = 0     # 제일 늦게 지는 꽃

while blossom:

    if now_endDt >= endDt or now_endDt < blossom[0][0]:
        break
    for _ in range(len(blossom)):
        if now_endDt >= blossom[0][0]:
            if end <= blossom[0][1]:
                end = blossom[0][1]

            blossom.remove(blossom[0])
        else:
            break
    now_endDt = end
    cnt+=1

if now_endDt <= endDt:
    print(0)
else:
    print(cnt)