인프런 커뮤니티 질문&답변

안녕하세요. sorting 파트의 문제 4번 심사위원 문제의 시간복잡도 질문입니다.

정답 코드에서 score를 순회하며 getAve 함수를 호출하면서 이중 for문이 실행됩니다.

score의 최대 길이가 30만이고, k가 최대 10만이므로 시간 복잡도는 O(nk)입니다.

최악의 경우 30만 × 10만 = 300억 번 연산이 발생하는데, 이는 1~2초의 제한 시간 내에 절대 수행될 수 없으므로 시간 초과가 발생하는 코드가 맞나요?

또한 제 풀이도 평가 부탁드립니다. 누적합 배열을 사용해서 풀어봤습니다. 이러면 시간복잡도가 O(nlogn)이 나와서, 최악의 경우라도 O(90만)이라고 계산했는데, 맞을까요?

import java.util.*;
class Solution {
    public int solution(int[] score, int k){
        int answer = 0, n = score.length;
        Arrays.sort(score);
        //pre: 누적합 배열
        int[] pre = new int[n];
        pre[0] = score[0];

        //누적합 구하기
        for(int i = 1; i < n; i++){
            pre[i] = pre[i-1] + score[i];
        }

        //score 순회하면서, 조건 만족하면 누적합 배열로 평균 구하기
        for(int i = 0; i <= n - k; i++){
            if(score[i + k - 1] - score[i] <= 10){
                int tmp;
                if(i == 0){
                    tmp = pre[i + k - 1];
                }else{
                    tmp = pre[i + k - 1] - pre[i - 1];
                }
                tmp /= k; //평균
                answer = tmp;
                break;
            }
        }
        return answer;
    }

    public static void main(String[] args){
        Solution T = new Solution();
        System.out.println(T.solution(new int[]{99, 97, 80, 91, 85, 95, 92}, 3));
        System.out.println(T.solution(new int[]{92, 90, 77, 91, 70, 83, 89, 76, 95, 92}, 4));
        System.out.println(T.solution(new int[]{77, 88, 78, 80, 78, 99, 98, 92, 93, 89}, 5));
        System.out.println(T.solution(new int[]{88, 99, 91, 89, 90, 72, 75, 94, 95, 100}, 5));
    }
}