글 읽기 - java 시간초과 해결 방법좀 알려주세

rhemddj5786 5년 전 0

최빈값 함수에서 시간초과가 되는 것 같습니다. 해결방법 좀 알려주세요

더불어, 배열의 크기가 몇 이상일때 부터 Scanner가 아닌 buffer를 사용해야 하나요?

package Sorting;
import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;

public class Statistics {
	/*sorting - Insertion Sort (삽입정렬) */
	public static void sort(int array[]) {
		int j,k,key;
		for(j=1; j<array.length; j++) {
			key=array[j];
			k=j;
			while(k>=1 && array[k-1]>key ) {
				array[k] = array[k-1];
				k--;
			}
			array[k]=key;
		}
	}
	
	/*평균 구하기*/
	public static int mean(int A[], int N) {
		int mean = 0;
		int sum = 0;

		//합 구하기
		for(int i = 0; i<A.length; i++) {
			sum = sum + A[i];
		}
		
		//소수 첫째자리에서 반올림
		mean = (int) Math.round((double)sum/N); //int나누기 int는 소수점버림
		
		return mean;
	}
	
	/*중앙값 구하기*/
	public static int median(int A[], int N) {
		int median = 0;
		sort(A);
		median = A[N/2];
		return median;
	}
	
	/*최빈값 구하기*/
	public static int mode(int A[], int N) {
		int mode = 0;
		int maxCount = 0; //count의 최대값
		int count[] = new int[8001]; //주어진 수들의 '갯수'의 배열
		int candidate[] = new int[N]; //같은 갯수를 가진 '최빈값'들의 배열
		int tempIndex = 0;
		
		//원소들의 갯수(count)구하기 
		for(int i = 0; i<A.length; i++) {
			count[A[i]+4000]++; //배열의 원소 카운트
		}
		for(int j = 0; j<count.length; j++) {
			if(maxCount<count[j]) {//최빈값 후보(동일한 갯수를가진 것들)의 갯수 저장
				maxCount = count[j];
			}
		}
		
		//동일한 최빈값을 가진 수들을 배열에 담는다
		for(int i = 0; i<count.length; i++) {
			if(count[i]==maxCount) {//최빈값 후보를 배열에 담는다
				candidate[tempIndex] = i-4000;
				tempIndex++;
			}
		}
		
	
		//두번째로 작은 값 찾기
		int candidateCount = 0; 
		for (int j = 0; j<candidate.length; j++) {//최빈값 후보의 갯수(0이 아닌 값) 구하기
			if(candidate[j] != 0) {
				candidateCount++;
			}
		}
		
		if(candidateCount > 2) { //최빈값 후보가 여러개인 경우
			mode = candidate[1];
		}
		else if(candidateCount <= 2) { //최빈값 후보가 1개 또는 2개인 경우
			mode = candidate[0];
		}

		return mode;

	}

	/*범위 구하기*/
	public static int range(int A[], int N) {
		int range = 0;
				
		sort(A);
		range = A[N-1] - A[0];
		
		return range;
		
	}
	

	public static void main(String[] args) throws Exception {
		// TODO Auto-generated method stub
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		int N = Integer.parseInt(br.readLine());
		int A[] = new int[N];
		
		for(int i = 0; i<A.length; i++) {
			A[i] = Integer.parseInt(br.readLine());
		}
		br.close();

		BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
		bw.write(Integer.toString(mean(A,N)) + "\n");
		bw.write(Integer.toString(median(A,N)) + "\n");
		bw.write(Integer.toString(mode(A,N)) + "\n");
		bw.write(Integer.toString(range(A,N)) + "\n");
		bw.close();
	
	}

}

djm03178 5년 전 2

최빈값이 문제가 아니라 sort가 문제입니다. 시간복잡도를 보면, 최빈값을 구하는 부분에서는 O(N)의 반복문이 몇 개 있는 것 뿐이지만, sort는 삽입 정렬을 쓰고 있어 단 하나의 이중루프일 뿐이지만 O(N^2)의 시간복잡도를 가집니다.

다른 효율적인 정렬 (병합 정렬, 힙 정렬) 등을 구현하거나, 내장 정렬 함수를 쓰는 것이 낫습니다.

rhemddj5786 5년 전 0

자세한 설명 감사합니다. 해결됐습니다. 감사합니다.

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

문제

문제

출처

ICPC

java 시간초과 해결 방법좀 알려주세

rhemddj5786 5년 전 0

djm03178 5년 전 2

rhemddj5786 5년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말