[프로그래머스 LV 3] 야근 지수 (파이썬/python)

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

코딩테스트 연습 - 야근 지수

 

(맨 처음 풀이)

n번의 반복문을 돌며

works 안에 있는 값 중에 가장 최대인 값에서 1씩 빼주는 식으로 만들었다.

그랬더니 테스트케이스는 잘 풀리는데 효율성 테스트에서 시간초과가 난다.

내가 짠 코드의 시간복잡도는 max( len(works) , n ) 이다. 

 

이 뜻은 뭐냐.. 로직은 맞는데 효율적으로 풀지 못 했단 소리다

효율적으로 푸는 방법을 고민해보자

 

(두번째로 고안한 풀이)

두번째로 고안한 풀이는 이분탐색이다.

입출력 예 1번을 그림으로 풀어보자.

문제는 이런 상황이면 좋지만

이 풀이는 균일한 높이에서 모든 막대를 잘라야한다.

야근지수 라는 문제는 한 막대에서만 자르는 상황도 있기때문에 이 풀이는 부적합하다.

 

(세번째로 고안한 풀이)

맨 아래 첫 번째 풀이 코드를 보자.

첫번째 풀이에서 내가 최대값을 구해 그것에 따른 인덱스를 구하는걸 보면

max함수 시간복잡도 O(N) , index함수는 시간복잡도를 찾아보진 않았지만 대충 빠른 탐색기법을 사용한다고 가정하고 생각해도 nlogn 이다. 즉 저 식에서만 선형탐색과정을 빼고 n^2logn 을 쓴걸 봤는데 그렇다면 저 최대값과 인덱스를 구하는 계산의 시간복잡도를 줄이면 되지 않을까 

 

nlogn으로 줄일 수 있다. 최대힙을 사용하면 된다.

 

(세번째풀이 // 합격)

from heapq import heappush, heappop
 
 
def solution(n, works):
    answer = 0
    hq = []
    # 최대힙 구성
    for w in works:
        heappush(hq, -w)
 
    for n in range(n):
        a = -heappop(hq)
        if a != 0:
            a -= 1
        heappush(hq, -a)
 
    for _ in range(len(hq)):
        answer += heappop(hq) ** 2
 
    return answer

 

 

 

 

 

(맨처음풀이 / 효율성 시간초과)

def solution(n, works):
    answer = 0
 
    for i in range(n):
        idx = works.index(max(works))
        if works[idx] != 0:
            works[idx] -= 1
 
    for w in works:
        answer += + w ** 2
 
    return answer