글 읽기 - Java11 시간초과 질문드립니다.

sunshins 3년 전 0

안녕하세요

Java11 시간초과 오류가 발생하는데 어떤 부분이 잘못 되었는지 알려주시면 감사드리겠습니다.

StringBuilder 도 사용해보았지만 같은 오류가 발생합니다.

감사합니다.

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.ArrayList;
import java.util.Arrays;

public class Main {
	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[] inputArray = new int[N];
		ArrayList<Integer> dupCheck = new ArrayList<Integer>();

		int avg, middleValue, repeatValue = 0, rangeValue, sum = 0;

		for (int i = 0; i < N; i++) {
			inputArray[i] = Integer.parseInt(br.readLine());
			sum += inputArray[i];
		}

		if (N == 1) {
			avg = inputArray[0];
			middleValue = inputArray[0];
			repeatValue = inputArray[0];
			rangeValue = 0;
		} else {
			// 산술값
			avg = (int) Math.round((double) sum / N);

			Arrays.sort(inputArray);
			// 중앙값
			middleValue = inputArray[N / 2];
			// 범위
			rangeValue = inputArray[N - 1] - inputArray[0];

            // 최빈값
			for (int i = 0; i < N; i++) {
				for (int j = i + 1; j < N; j++) {
					if (inputArray[i] == inputArray[j] && !dupCheck.contains(inputArray[i])) {
						dupCheck.add(inputArray[i]);
					}
				}
			}

			if (dupCheck.isEmpty()) {
				repeatValue = inputArray[1];
			} else {
				if (dupCheck.size() == 1 || dupCheck.size() == 2) {
					repeatValue = dupCheck.get(0);
				} else {
					repeatValue = dupCheck.get(1);
				}
			}
		}

		bw.write(avg + "\n" + middleValue + "\n" + repeatValue + "\n" + rangeValue + "\n");
		bw.close();

	}
}

nahwasa 3년 전 0

최빈값 계산에서 시간초과가 납니다.

2중 반복문에서 O(N^2) = 최대 50만 x 50만 = ?!!

1억번에 1초정도로 대강 잡으시면 되므로 당연히 시간초과가 나게 됩니다.

최빈값을 계산하는 로직을 다른 방법으로 한번 생각해보세요!

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

문제

문제

출처

ICPC

Java11 시간초과 질문드립니다.

sunshins 3년 전 0

nahwasa 3년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말