[프로그래머스] 예산: O(n^2) -> O(n log n)

문제 링크

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

프로그래머스

 

O(n^2)

def solution(d, budget):
    d.sort() 
    while sum(d) > budget:
        d.pop()      
    return len(d)

 

sum()을 이용해 간단하게 푼 방법 but..

1. d.sort()

• 시간 복잡도: O(n log n)
• sort()는 Timsort 알고리즘을 사용하므로 리스트 크기 n에 대해 O(n log n)의 시간이 걸립니다.

2. while sum(d) > budget:

• sum(d)의 시간 복잡도는 리스트 내 모든 요소의 합을 구하는 작업으로, O(n)입니다.
• while 루프 내에서 sum(d)는 매번 반복되므로, 가장 나쁜 경우는 d의 모든 요소를 하나씩 제거하는 상황입니다. 즉, 루프는 최악의 경우 n번 반복되며, 매번 O(n)의 시간이 걸립니다. -> O(n^2)

3. d.pop()

• 리스트의 마지막 요소를 제거하는 pop()은 O(1)입니다. 따라서, 이 부분은 루프 내에서 시간 복잡도에 크게 영향을 미치지 않습니다.

최종 시간 복잡도:

• O(n^2)

개선 방법: sum(d)를 루프 안에서 매번 계산하는 대신, budget에서 각 요소를 하나씩 빼나가면 시간 복잡도를 줄일 수 있다.

 

O(n log n)

def solution(d, budget): 
    d.sort()
    count = 0
    
    for cost in d:
        if budget - cost >= 0:
            budget -= cost
            count += 1
        else:
            break
            
    return count

개선된 로직의 시간 복잡도:

1. d.sort(): O(n log n) - 예산이 작은 부서부터 처리하기 위해 정렬.
2. for 루프: O(n) - 각 부서의 소요 비용을 하나씩 처리하면서 예산에서 차감.

최종 시간 복잡도:

• O(n log n)

이 코드는 매번 sum(d)를 다시 계산하는 부분을 개선했다.

 

실행 결과 비교

일부 테스트에서 확연한 차이가 보인다

 

 

 

 

 

다시 한번 짧은 코드가 좋은 코드가 아님을 명심,,