[알고리즘] 정렬

sort와 sorted의 차이

1) sort
list 클래스의 메서드
반환하는 것은 none. 전달받은 객체를 정렬함

2) soted
iterable 객체(list, tuple, string, dict, set 등.)을 파라미터로 받을 수 있는 메서드
정렬된 객체를 리스트로 반환

힙 정렬

heapq 모듈은 이진 트리(binary tree) 기반의 최소 힙(min heap) 자료구조를 제공. 자바에서는 PriorityQueue 클래스

문제1) 디펜스 게임

풀이)

from copy import deepcopy
from heapq import heappop, heappush

def solution(n, k, enemy):
    answer, sumEnemy = 0, 0
    heap = []
    
    for e in enemy:
        heappush(heap, -e)
        sumEnemy += e
        if sumEnemy > n:
            if k == 0: break
            sumEnemy += heappop(heap) 
            k -= 1
        answer += 1
    return answer

문제1) 호텔 대실

풀이)

from heapq import heappush, heappop
def solution(book_time):
    
# 1. 단순한 풀이
#     answer = 0
#     time_tables = [0 for _ in range((60 * 24)+1)]
    
#     def changeMinute(time):
#         s_t = int(time[:2]) * 60 + int(time[3:]) 
#         return int(time[:2]) * 60 + int(time[3:])
    
#     for b_t in book_time:
#         s_t, e_t = changeMinute(b_t[0]), changeMinute(b_t[1])
#         if e_t > (60 * 24) - 10:
#             e_t = (60 * 24) - 10
#         for t in range(s_t+1, e_t+11):
#             time_tables[t] += 1
#     answer = max(time_tables)

# 2. heap을 이용한 풀이
    answer = 0
    rooms = []
    book_minute = []
    
    tmp_book_time = [[int(time[0][:2]) * 60 + int(time[0][3:]), int(time[1][:2]) * 60 + int(time[1][3:])] for time in book_time]
    # tmp_book_time.sort()
    # tmp_book_time.sort(key=lambda x : x[0])
    tmp_book_time = sorted(tmp_book_time, key=lambda x: x[0])
    print(tmp_book_time)
    
    for b_t in tmp_book_time:
        s_t, e_t = b_t[0], b_t[1]

        
        if len(rooms) == 0:
            heappush(rooms, e_t)
        else:
            if rooms[0] + 10 <= s_t:
                heappop(rooms)
            heappush(rooms, e_t)
    answer = len(rooms)
    print(rooms)
    return answer