알고리즘 - 과일장수 (시간복잡도 줄이기)

결과 400초->100초

같이한팀원

• https://kmy9810.tistory.com/
• https://dawnpast12.tistory.com/

김묭의 자기개발

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

def solution(k, m, score):
    score.sort(reverse=True)
    li_1 = []
    li_2 = []
    answer = 0
    for i in score:
        if len(li_2) == m:
            li_1.append(li_2)
            li_2 = [i]
        else:
            li_2.append(i)
            if len(li_2) == m:
                li_1.append(li_2)
                li_2 = []
    for j in li_1:
        answer += min(j)*m

    return answer

1.작동 안하는 code 삭제 (if문 제거)

2.list 사용 줄이기

def solution(k, m, score):
    score.sort(reverse=True)
    num_box = len(score)//m
    answer = 0
    box = []

    for i in range(num_box):
        box.append(score[i*m:(i+1)*m])

    for j in box:
        answer += j[-1]*m

    return answer

 

 

3. for문 합치기

4.append 지우고 int값 합치기

for문 안에서 *를 밖으로 빼서 불필요한 계산 줄이기

def solution(k, m, score):
    score.sort(reverse=True)
    num_box = len(score)//m
    answer = 0

    for i in range(num_box):
        answer += score[(i+1)*m-1]

    answer *= m

    return answer

 

 

 

 

 

 

---

1번째 방식

테스트 1 〉	통과 (0.03ms, 10.3MB)
테스트 2 〉	통과 (0.01ms, 10.2MB)
테스트 3 〉	통과 (0.05ms, 10.3MB)
테스트 4 〉	통과 (0.01ms, 10.2MB)
테스트 5 〉	통과 (0.02ms, 10.2MB)
테스트 6 〉	통과 (30.11ms, 12.5MB)
테스트 7 〉	통과 (41.24ms, 11.8MB)
테스트 8 〉	통과 (5.08ms, 10.4MB)
테스트 9 〉	통과 (30.24ms, 12MB)
테스트 10 〉	통과 (37.15ms, 11.8MB)
테스트 11 〉	통과 (404.16ms, 36.4MB)
테스트 12 〉	통과 (478.94ms, 34MB)
테스트 13 〉	통과 (537.65ms, 36.3MB)
테스트 14 〉	통과 (495.10ms, 37.1MB)
테스트 15 〉	통과 (422.96ms, 39.3MB)
테스트 16 〉	통과 (0.01ms, 10.2MB)
테스트 17 〉	통과 (0.01ms, 10.2MB)
테스트 18 〉	통과 (0.04ms, 10.1MB)
테스트 19 〉	통과 (0.04ms, 10.2MB)
테스트 20 〉	통과 (0.03ms, 10.2MB)
테스트 21 〉	통과 (0.01ms, 10.4MB)
테스트 22 〉	통과 (0.01ms, 10.2MB)
테스트 23 〉	통과 (0.01ms, 10.3MB)
테스트 24 〉	통과 (0.02ms, 10.3MB)

2번째 방식

테스트 1 〉	통과 (0.02ms, 10.2MB)
테스트 2 〉	통과 (0.01ms, 10.3MB)
테스트 3 〉	통과 (0.02ms, 10.1MB)
테스트 4 〉	통과 (0.01ms, 10.2MB)
테스트 5 〉	통과 (0.01ms, 10.1MB)
테스트 6 〉	통과 (12.80ms, 12.5MB)
테스트 7 〉	통과 (9.76ms, 11.6MB)
테스트 8 〉	통과 (1.95ms, 10.4MB)
테스트 9 〉	통과 (12.47ms, 12.1MB)
테스트 10 〉	통과 (12.62ms, 11.7MB)
테스트 11 〉	통과 (196.95ms, 36.3MB)
테스트 12 〉	통과 (153.18ms, 34.1MB)
테스트 13 〉	통과 (192.84ms, 36.3MB)
테스트 14 〉	통과 (136.47ms, 32.6MB)
테스트 15 〉	통과 (155.19ms, 34MB)
테스트 16 〉	통과 (0.00ms, 10.2MB)
테스트 17 〉	통과 (0.01ms, 10.2MB)
테스트 18 〉	통과 (0.03ms, 10.3MB)
테스트 19 〉	통과 (0.02ms, 10.2MB)
테스트 20 〉	통과 (0.02ms, 10.3MB)
테스트 21 〉	통과 (0.01ms, 10.4MB)
테스트 22 〉	통과 (0.01ms, 10.1MB)
테스트 23 〉	통과 (0.01ms, 10.3MB)
테스트 24 〉	통과 (0.01ms, 10.3MB)

3번째 방식

테스트 1 〉	통과 (0.01ms, 10.1MB)
테스트 2 〉	통과 (0.01ms, 10.2MB)
테스트 3 〉	통과 (0.03ms, 10.2MB)
테스트 4 〉	통과 (0.01ms, 10.3MB)
테스트 5 〉	통과 (0.01ms, 10.2MB)
테스트 6 〉	통과 (6.73ms, 10.9MB)
테스트 7 〉	통과 (6.25ms, 11MB)
테스트 8 〉	통과 (0.91ms, 10.4MB)
테스트 9 〉	통과 (6.73ms, 10.9MB)
테스트 10 〉	통과 (5.20ms, 10.5MB)
테스트 11 〉	통과 (91.55ms, 21.5MB)
테스트 12 〉	통과 (85.82ms, 21.5MB)
테스트 13 〉	통과 (96.49ms, 21.7MB)
테스트 14 〉	통과 (80.78ms, 21.7MB)
테스트 15 〉	통과 (84.75ms, 21.6MB)
테스트 16 〉	통과 (0.00ms, 10.3MB)
테스트 17 〉	통과 (0.00ms, 10.2MB)
테스트 18 〉	통과 (0.02ms, 10.3MB)
테스트 19 〉	통과 (0.01ms, 10.2MB)
테스트 20 〉	통과 (0.01ms, 10.2MB)
테스트 21 〉	통과 (0.00ms, 10.1MB)
테스트 22 〉	통과 (0.00ms, 10.2MB)
테스트 23 〉	통과 (0.01ms, 10.2MB)
테스트 24 〉	통과 (0.00ms, 10.2MB)