배상 비용 최소화

처음에 문제를 읽었을 때 이게 뭔소린가했는데 금방 이해했다. 뭐 대충 제일 큰수를 줄이면 배상비용이 최소가 되니까 제일 큰 수를 깎는것을 반복해야한다고 생각함

def solution(no, works):
    result = 0

    # 제일 큰 수를 일해야지 비용이 최소화가 된다. -> 큰 수를 깎아야함
    while no > 0 :
        works.sort()
        works[-1] -= 1
        no -= 1
        
    for n, i in enumerate(works):
        works[n] = i*i

    return sum(works)

ㅜㅜ

 

def solution(no, works):
    result = 0

    # 제일 큰 수를 일해야지 비용이 최소화가 된다. -> 큰 수를 깎아야함
    while no > 0 :
        works.sort()
        if works[-1] == 0:
            break
        works[-1] -= 1
        no -= 1
        
    for n, i in enumerate(works):
        works[n] = i*i

    return sum(works)

제일 큰 수에 깍을 작업이 없을 때를 고려를 안해서 테스트에 통과 못한듯! 고쳐줬더니 통과함 룰루

 

 

 

코드 리뷰

• 배상 비용 최소화 문제는 우선 순위 큐를 사용해 푸는 것이 정석
• 가지치기
• list comprehension을 이용

가지치기가 뭔가,,

 

 

우선 순위 큐

heapq를 사용해서 우선순위 큐를 생성할 수 있다.

import heapq

첫번째 인자는 heap 자체인 list이고, 두번째 인자는 튜플인데 튜플의 첫번째 요소는 우선순위 값, 두번째 요소는 데이터를 넣어주면 된다. 함수의 두번째 인자를 튜플이 아닌 일반 값을 넣어주면, 값을 기준으로 heap을 만들어준다. 파이썬이 제공하는 힙은 최소힙이므로 주의하도록하고 삽입 별 시간 복잡도는 O(logN)이다.

 

Heap에 요소 추가하기 - heappush(배열이름, (우선순위, 요소))

testheap = []
heapq.heappush(testheap, (3, "우선순위 3"))
heapq.heappush(testheap, (4, "우선순위 4"))
heapq.heappush(testheap, (8, "우선순위 8"))
heapq.heappush(testheap, (1, "우선순위 1"))
heapq.heappush(testheap, (10, "우선순위 10"))

 

Heap에 요소 삭제하기 - heappop(배열이름)

heapq.heappop(heaptest)

 

 

우선순위 큐를 사용한 문제 풀이

import heapq

def pqsolution(no, works):
    if no > sum(works):
        return 0
    else:
        # 큰 값이 우선 순위가 높아야하니까 -를 붙여서 우선순위를 담는다.
        works = [(-i, i) for i in works]
        heapq.heapify(works) # 힙으로 만들기 (우선순위에 따라 정렬됨)
        print("우선순위 큐: {}".format(works))

        for _ in range(no):
            # 제일 큰 값이 루트에 있으니 꺼냄
            # 루트 꺼내서 우선순위 말고 값 -1을 해준다.
            work = heapq.heappop(works)[1] - 1

            # 일을 한 후 다시 우선순위 큐에 저장
            heapq.heappush(works, (-work, work))

        return sum(i[1] ** 2 for i in works)