[프로그래머스] 문제풀이 - 야근 지수

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

프로그래머스

첫 풀이

1. 정렬을 하고 리스트의 맨 앞을 1씩 뺀다

2. n==0이 될 때까지 과정 1을 반복한다

 

def solution(n, works):
    works.sort(reverse=True)
    while n!=0 and sum(works)>0:
        if works[0]>works[1]:
            works[0]-=1
        else:
            works[0]-=1
            works.sort(reverse=True)
        n-=1

    hap=sum(list(map(lambda x: x **2, works)))
    
    return hap

시간 초과가 발생했습니다.

 

두번째 풀이

1. 정렬이 시간을 많이 잡아먹는거같아서 사용하지 않기

2. 리스트에서 가장 큰 원소를 찾아 1을 빼준다

3. n==0이 될 때까지 과정 2를 반복한다

def solution(n, works):
    
    if sum(works)<=n:
        return 0
    
    while n!=0:
        max_value=max(works)
        works[works.index(max_value)]-=1
        n-=1
        
    hap=sum(list(map(lambda x: x **2, works)))
    
    return hap

통과할줄 알았는데 또 시간 초과가 발생했습니다...

더 나은 답안

1. 검색을 해보니까 heapq이라는 구조를 사용해야했다.

2. heapq는 최소값으로 계속 정렬해주는 구조다

3. 최소값으로 정렬이 되므로 -를 사용하면 최대값을 구할 수 있다.

 

import heapq

def solution(n, works):
    if sum(works)<=n:
        return 0
    
    works=[-w for w in works]
    heapq.heapify(works)
    # heap=[]
    # for i in works:
    #     heapq.heappush(heap,-i)
    
    while n>0:
        max_val=heapq.heappop(works)
        heapq.heappush(works,max_val+1)
        n-=1
        
    hap=sum(list(map(lambda x: x **2, works)))
    
    return hap

 

배운 점

1. heapq 자료구조를 배웠다

2. 최대값이나 최소값을 구할때 리스트 개수가 많은 경우 heapq를 사용해야겠다

3. 값을 넣을때 heapq.heappush(힙 리스트, 값)

4. 값을 삭제할때 heapq.heapop(힙 리스트)

5. 리스트를 힙 구조로 변경할때 heapq.heapify(힙 리스트)

 

추가로

heapq 구조에서 주의할 점은 모든 리스트가 정렬되지는 않는다는 것입니다.

a[0]이 제일 작다고 해서 a[1]이 두번째작고 a[2]이 세번째로 작지가 않습니다.

heappop이라는 함수가 원소를 삭제할 때마다 이진 트리의 재배치를 통해서 새로운 최소값을 정렬하기 때문입니다.

 

그래서 최소값을 얻으려면 heappop을 통해 재배치를 하고 접근해야합니다.