240721 TIL

1.  알고리즘 과일장수 문제 시간 초과

👉문제 바로 가기

수정 전 코드이다.

배열을 정렬한 뒤 슬라이싱해서 새로운 배열을 만들고 점수를 합산한다. k 값은 나의 코드 상 쓰이지 않는다.

def solution(k, m, score):
    score.sort(reverse=True)
    sum = 0
    for i in range(len(score)//m):
        sum += m * score[m-1]
        score = score[m:]
    return sum

어...어라 이게 아닌데...

이 문제가 시간초과인 이유는 다음과 같다.

• O(n)의 시간 복잡도 : 슬라이싱 할 경우 시간 복잡도가 크게 증가한다.
• 불필요한 정렬: 문제의 요구사항에 따라 k*m개의 최대 원소만 필요하다.

 

수정된 코드

def solution(k, m, score):
    score.sort(reverse=True)
    return sum(score[i] for i in range(m-1, len(score), m)) * m

• 점수를 내림차순으로 정렬한다. (높은 점수부터 낮은 점수 순으로)
• range(m-1, len(score), m)을 사용하여 각 상자의 마지막 사과(가장 낮은 점수) 인덱스를 선택한다.

 

휘유...