[프로그래머스] Level2 호텔 대실(python)

https://school.programmers.co.kr/learn/challenges?order=recent&levels=2%2C3&languages=python3 

코딩테스트 연습 | 프로그래머스 스쿨

 

1. 내가 작성한 코드

 

heap을 이용하면 될 것 같다는 생각을 하긴 했는데, 그냥 문자열로 풀었다.

 

이유는.. 나도 모른다.. 아마 내가 고집쟁이기 때문.. 결국 반례를 하나 못 찾아서 3시간 걸려서 풀었다.

 

=> 반례 : 방 청소가 끝났을 때 23:59분이 넘어가면 방을 빌려줄 수 없는데 00:50 등의 시간이 들어오면 빌려주게 됨

ex) ["23:50", "23:59"],["00:10", "23:59"]] 

 

def solution(book_time):
    #입실 기준으로 정렬
    book_time.sort()
    
    new_book = [[] for _ in range(len(book_time))]
    
    #book_time이 문자열로 되어있으니 int로 바꿔서 새로운 list에 넣음
    
    for i in range(len(book_time)):
        for j in range(2):
            a, b = map(int,book_time[i][j].split(":"))
            new_book[i].append(a)
            new_book[i].append(b)
    
    cnt = 1
    
    next = new_book[0]
    
    while new_book:
        
        #new_book에서 next값 삭제
        new_book.remove(next)
        
        # 청소를 마친 시간이 23:59 를 넘어가면 next time을 23:59로 바꿔줌으로써 빌려줄 수 없게 함
        if ((next[3] + 10) // 60 + next[2]) >= 24:
            next_hh = 23
            next_mm = 59
        # 23:59를 넘어가지 않으면 제대로 next 타임을 만들어 줌
        else: 
            next_hh = ((next[3] + 10) // 60 + next[2]) % 24  #(분을 60으로 나눈 몫 + 시간)을 24로 나눈게 시간
            next_mm = (next[3] + 10) % 60 #60으로 나눈 나머지가 분
        
        
        check = 0
        
        #끝나는 시간보다 처음 시간이 늦으면 동일한 방 빌려줌
        for j in new_book:
            if j[0] > next_hh or (j[0] == next_hh and j[1] >= next_mm):
                next = j
                check += 1
                break
        
        #끝나는 시간보다 처음 시간이 늦는 방이 없으면 새로운 방 빌려줌
        if new_book and check == 0:
            cnt+=1
            next = new_book[0]
            
        if not new_book:
            return cnt

 

2. heap을 이용한 코드

import heapq

def solution(book_time):
    
    #분으로 바꿔서 새로운 list에 넣기 ex) 10:00, 11:00 => 600,660
    new_book = [(int(start[:2]) * 60 + int(start[3:]), int(end[:2]) * 60 + int(end[3:])) for start, end in book_time]  
    new_book.sort()
    
    answer = 1
    heap = []
    
    for start, end in new_book:
    	# heap이 비어있으면 넣어줌
        if not heap:
            heapq.heappush(heap,end+10)
            continue
        if heap[0] <= start:
            heapq.heappop(heap)
        else:
            answer+=1
            
        heapq.heappush(heap,end+10)
        
    return answer

 

자세한 풀이는 아래 링크를 참고했다.

 

https://velog.io/@isayaksh/%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98-Programmers-%ED%98%B8%ED%85%94-%EB%8C%80%EC%8B%A4-Python

[알고리즘] Programmers 호텔 대실 #Python