[Programmers / Level3] 야근지수

 

https://school.programmers.co.kr/learn/courses/30/lessons/12927

프로그래머스

---

 

<내 코드> - 오답

• 시간복잡도 고려를 하지않고, 단순히 역순정렬을 하고 가장 큰 숫자부터 선형적으로 숫자를 뺄셈해주는식으로 해버렸다.

def solution(n, works):
    sorted_works = sorted(works, reverse=True)
    for i in range(n):
        sorted_works[i % len(works)] -= 1
    
    for i in range(len(sorted_works)):
        works = sorted_works[i]
        if works < 0:
            sorted_works[i] = 0
            continue
        sorted_works[i] = works * works
        
    return sum(sorted_works)

망

 

다시한번, 처음부터 문제에서 고려해야하는 사항을 유의깊게 봤다.

 

1초당 어느만큼의 입력크기가 들어오는가?

“일반적으로, 알고리즘이 1초 내에 처리해야 하는 입력의 크기는 대략 10^7 ~ 10^8 정도입니다(단순 계산 기준)”

 

작업량 리스트를 매번 정렬하는 접근 방식은 O(NlogN)의 시간 복잡도를 가진다 (여기서 N은 works의 길이이다.)
만약 n번 모두 정렬한다면, 최악의 경우 시간 복잡도는 O(NlogN * n)이 될 수 있다. 제한 사항을 고려했을 때 매우 비효율적이다.

 

따라서, 선형 리스트 자료구조보다 logN 시간 복잡도를 가지는 최대힙을 사용해서 구해주었다.

 

 

힙의 삽입 및 삭제 연산

힙은 O(logN) 시간 복잡도를 가집니다. 따라서, n번의 연산에 대해 O(nlogN)의 시간 복잡도를 가집니다.

주어진 문제에서는 n번 반복하여 작업량을 1씩 줄여야 하므로, 가장 큰 작업량을 빠르게 찾고 수정하는 작업에 최소 힙(부호 반전을 통한 최대 힙 사용)을 사용하는 것이 적절하다.

 

따라서, 시간복잡도가 낮은 힙을 사용하는것이 옳은 풀이이다. 결론적으로 heapq를 사용하여 Nlogn으로 풀어내야한다.

 

 

<정해코드>

import heapq

def solution(n, works):
    work = [-work for work in works]
    heapq.heapify(work)
    
    while n > 0:
        max_work = heapq.heappop(work)
        if max_work == 0: break
        heapq.heappush(work, max_work + 1)
        n -= 1
    
    return sum(w ** 2 for w in work)

 

 

짤막팁)

여기서 하나 더 나아가, walrus operator (':=' 연산자) 를 사용해서 표현식 내에서 값의 할당과 평가를 동시에 수행할 수 있다.

단, python3.8 이상부터 사용가능하기 때문에 버전에 주의해야한다.

 

# 기존의 코드 방식

n = len(my_list)
if n > 10:
    print(f"List is too long ({n} elements)")

 

# Walrus 연산자를 사용한 방식

if (n := len(my_list)) > 10:
    print(f"List is too long ({n} elements)")

 

<Walrus 연산자를 사용한 정해풀이>

from heapq import heapify, heappush, heappop

def solution(n, works):
    heapify(works := [-i for i in works])
    for i in range(min(n, abs(sum(works)))):
        heappush(works, heappop(works)+1)
    return sum([i*i for i in works])

 

왈루스 연산자를 사용하면 코드를 더 간결하게 작성할 수 있게 된다.