글 읽기 - 자바 시간초과

piz122 2년 전 0

어떤 부분때문에 시간초과가 나는 지 모르겠습니다.

import java.io.*;
import java.util.*;

public class Statistics {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        int N = Integer.parseInt(br.readLine());

        int[] array = new int[N];
        int[] count = new int[8001]; // 절대값4000 -> *2 에러로 인한 +1
        ArrayList<Integer> save = new ArrayList<>();

        int sum = 0; // 1번을 구하기위한 모두 더한 값
        for (int i = 0; i < N; i++) {
            int num = Integer.parseInt(br.readLine());
            array[i] = num;
            sum += array[i];
            count[array[i] + 4000]++;
        }
        double avg = Math.round((double) sum / N);
        bw.write((int)avg + "\n"); // 1번


        mergeSort(array, 0, array.length - 1);

        bw.write(array[N / 2] + "\n"); // 2번


        int max = 0;
        for (int i = 0; i < N; i++) { // 4000을 더해주어 음수값을 변환
            max = Math.max(max, count[array[i] + 4000]);
        }

        for(int i=0; i<N; i++){
            if(max == count[array[i]+4000]){
                save.add(array[i]);
                count[array[i]+4000]--;
            }
        }

        if(save.size() > 1){ // save가 2개 이상이면 같은 빈도수의 수가 있는 것
            bw.write(save.get(1) + "\n"); // 2번째 것을 출력 (이미 정렬 되어있는 상태)
        } else {
            bw.write(save.get(0) + "\n");
        }


        bw.write(Math.abs(array[array.length - 1] - array[0]) + "\n"); // 4번


        bw.close();
        br.close();
    }

    static void mergeSort(int[] array, int low, int high) { //합병정렬
        int[] temp = new int[array.length];
        if (low < high) {
            int mid = (low + high) / 2;

            mergeSort(array, low, mid);
            mergeSort(array, mid + 1, high);

            int start = low;
            int end = mid + 1;
            int index = start;

            while (start <= mid || end <= high) {
                if (end > high || (start <= mid && array[start] < array[end])) {
                    temp[index++] = array[start++];
                } else {
                    temp[index++] = array[end++];
                }
            }
            for (int i = low; i <= high; i++) {
                array[i] = temp[i];
            }
        }

    }
}

nahwasa 2년 전 1

mergeSort 때문입니다.

해당 부분 개선해보시거나, 그냥 Arrays.sort 로만 변경하시면 통과 되셔요.

piz122 2년 전 0

와... 그렇네요. 감사합니다

댓글을 작성하려면 로그인해야 합니다.

문제

문제

출처

ICPC

자바 시간초과

piz122 2년 전 0

nahwasa 2년 전 1

piz122 2년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말