글 읽기 - (Java) 최빈값을 시간 소모 없이 찾을 수 있나요?

qorrhktk66 3년 전 0

현재 제 코드에서 오름차순 배열 정렬, 최빈값 추적에서 시간을 먹고 시간초과가 뜨는 것 같은데..

오름차순 정리는 무조건 필요하다고 보고, (중간값과 범위 구할때 어차피 반복문 돌려야 할 것 같음)

최빈값도 저에겐 저게 최선이었는데..

반복문을 줄일 방법이 안떠오릅니다.

package 백준;

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.Set;
import java.util.TreeSet;

public class Main {
	public static void main(String[] args) {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
		try {
			int N = Integer.parseInt(br.readLine());
			int[] num = new int[N];
			for (int i = 0; i < N; i++) {
				num[i] = Integer.parseInt(br.readLine());
			}
			//오름차순으로 배열 정렬
			for (int i = 0; i < N; i++) {
				for (int j = i + 1; j < N; j++) {
					if (num[i] > num[j]) {
						int temp = num[i];
						num[i] = num[j];
						num[j] = temp;
					}
				}
			}
			double sum = 0;
			int avg = 0;
			int mid = 0;
			int maxCount = 0;
			int dif = 0;
			for (int i = 0; i < N; i++) {
				sum += num[i];
			}
			// 최빈값 인덱스 추적
			int[] count = new int[N];
			for (int i = 0; i < N; i++) {
				for (int j = 0; j < N; j++) {
					if (num[i] == num[j]) {
						count[i]++;
					}
				}
			}
			// 빈도가 높았던 인덱스를 저장
			int max = 0;
			ArrayList<Integer> list = new ArrayList<Integer>();
			for (int i = 0; i < N; i++) {
				if (count[i] > max) {
					max = count[i];
				}
			}
			for (int i = 0; i < N; i++) {
				if (count[i] == max) {
					list.add(i);
				}
			}
			// set에 num의 최빈값들을 저장(중복 제거)
			Set<Integer> set = new TreeSet<Integer>();
			for (int i = 0; i < list.size(); i++) {
				set.add(num[list.get(i)]);
			}
			list.removeAll(list);
			list.addAll(set);

			
			
			avg = Integer.parseInt(String.format("%.0f", sum / N));
			mid = num[N / 2];
			if (list.size() == 1) {
				maxCount = list.get(0);
			} else {
				maxCount = list.get(1);
			}
			dif = num[N - 1] - num[0];
			
			bw.write(avg + "\n" + mid + "\n" + maxCount + "\n" + dif);
			bw.close();
		} catch (

		IOException e) {
			e.printStackTrace();
		}
	}
}

ohsemin4 3년 전 1

먼저 오름 차순 정렬을 할때 저렇게 정렬을 하시면 시간 복잡도가 최대 O(N^2)이 나오게 됩니다.

배열을 정렬하실때는 Arrays.sort() 함수를 사용해보세요

qorrhktk66 3년 전 0

감사합니다. 좋은 함수 하나 배웠습니다.

하지만 최빈값 찾는데에 시간이 쓰이나 봅니다.. 해결은 못하겠네요

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

문제

문제

출처

ICPC

(Java) 최빈값을 시간 소모 없이 찾을 수 있나요?

qorrhktk66 3년 전 0

ohsemin4 3년 전 1

qorrhktk66 3년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말