글 읽기 - 자바 시간초과가 계속납니다..ㅠ

cjihong 2년 전 0

시간초과가 계속 나는데 Collection.sort()를 사용해서인가요..? 아니면 왜 시간 초과가 뜨는지 궁금합니다ㅠㅠ

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

public class _2108 {
    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 max=0, first=0, second=0;
        int hap=0;
        ArrayList<Integer> ar = new ArrayList<Integer>();
        for(int i=0; i<N; i++){
            int a = Integer.parseInt(br.readLine());
            ar.add(a);
            hap+=a;
        }
        Collections.sort(ar);
        for(int i=N-1; i>=0; i--){
            int a = Collections.frequency(ar,ar.get(i));
            if(a>=max){
                max = a;
                int aa = first;
                first = ar.get(i);
                second = aa;
            }
            i-=a-1;
        }
        bw.write((int)Math.round((double) hap/N)+"\n");
        bw.write(ar.get(N/2)+"\n");
        bw.write(((second!=0)?second:first)+"\n");
        bw.write(ar.get(ar.size()-1)-ar.get(0)+"\n");
        bw.flush();
        bw.close();
    }
}

336699go 2년 전 0

안녕하세요! Collection.sort()는 괜찮은 것 같은데 18~27번째 줄에서 시간복잡도가 O(n^2)이라 시간초과가 나는 것 같아요

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

문제

문제

출처

ICPC

자바 시간초과가 계속납니다..ㅠ

cjihong 2년 전 0

336699go 2년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말