[백준] 18110번_solved.ac(Java)

문제 풀이

백준의 18110번 문제입니다. 문제 출처

(1) 문제 파악

점수가 주어지고 해당 점수들의 30% 절사 평균을 구하는 문제입니다.

(2) 문제 풀이 방법 생각하기

30% 절사 평균으로 정해져 있으니 주어진 수의 개수 N개 중 위, 아래로 Math.round(N * 0.15)개를 빼고 평균을 계산해주면 됩니다.

N개의 점수를 입력받아 저장하고, 오름차순으로 정렬한 뒤에 계산해주면 됩니다!

(3) 시간 복잡도 확인

시간 제한은 1초 입니다. 즉, 대략 1억번 연산 안에 문제를 해결해야 합니다.

n의 최대 값은 \(3 * 10^5\) 입니다. 점수를 배열에 저장하고 Arrays.sort()를 사용해 정렬하면 평균적으로 O(nlogn)의 시간 복잡도를 가지므로 가능합니다!

(4) 구현

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

public class Main {
    static final double percent = 0.15;
    
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int N = Integer.parseInt(br.readLine());
        double result;
        int[] score = new int[N];
        
        if(N == 0) result = 0;
        else { 
            int p = (int) Math.round(N*percent);
            double sum = 0;
            for(int i=0; i<N; i++) {
                score[i] = Integer.parseInt(br.readLine()); 
                sum += score[i];
            }
            Arrays.sort(score);

            int count = 0;
            while(count<p) {
                sum -= score[count];
                sum -= score[score.length-1-count];
                count++;
            }

            result = Math.round(sum/(N-p-p));
        }

        System.out.println((int)result);
        br.close();
    }
}