[백준] solved.ac (in Java)

📍 문제

https://www.acmicpc.net/problem/18110

 

상,하위 15퍼센트 의견은 제외하고 평균을 낸 뒤 반올림하는 문제

쉬운 문제이지만 두 가지 방법으로 풀 수 있어서 글을 작성한다.

 

의견의 개수 n이 매우 크므로 이 부분에 유의 (0 ≤ n ≤ 3^105)

📍 코드 설명

첫번째 방법

가장 떠올리기 쉬운 방법

1. 의견을 배열에 받은 뒤 오름차순 정렬한다.

2. 상 하 15%를 계산한다.

3. 15%에 해당하는 index를 제외한 배열을 전부 더한 뒤 평균을 구한다

 

이 방법은 배열을 정렬할 때 평균 : O(nlog(n)) / 최악 : O(n^2),

전부 더할 때 입력의 수만큼 돌아야한다.

 

두번째 방법

countingSort를 이용한 방법

1. 배열 index를 점수라 생각하고, 점수가 들어올때마다 arr[index] += 1을 해준다

2. 상 하 15%를 계산한다

3. 하위 15% 의견을 제거한다

4. 상위 15% 점수를 제거한다

5. 배열을 전부 다 더한 뒤 평균을 구한다

 

이 방법은 정렬이 없고, 배열을 전부 다 더할 때도 30번만 돌기때문에 시간이 훨씬 빠르다

📍 코드

✔️ 첫번째 방법 코드

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

public class Main {

	public static void main(String...args) throws Exception {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		int n = Integer.parseInt(br.readLine());	//의견의 개수
		
		//제거할 인원 계산
		int removeCnt = (int)(n * 0.15 + 0.5);
		
		//의견 입력
		int[] arr = new int[n];
		for(int i = 0; i < n; i++) {
			arr[i] = Integer.parseInt(br.readLine());
		}
		
		//의견 정렬
		Arrays.sort(arr);
		
		//의견 계산
		double difficultySum = 0;
		for(int i = removeCnt; i < n - removeCnt; i++) {
			difficultySum += arr[i];
		}
		int answer = (int)(difficultySum / (n - removeCnt*2) + 0.5);
		
		System.out.println(answer);	
	}
}

✔️ 두번째 방법 코드

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

public class Main {

	public static void main(String...args) throws Exception {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		int n = Integer.parseInt(br.readLine());	//의견의 개수
		
		//제거할 인원 계산
		int removeCnt = (int)(n * 0.15 + 0.5);
		
		//의견 입력
		int[] arr = new int[31];
		for(int i = 0; i < n; i++) {
			int index = Integer.parseInt(br.readLine());
			arr[index] += 1;
		}
		
		//제외되는 사람 앞 부분 제거
		int idx = 1;
		int removed = 0;
		while(removed < removeCnt) {
			if (arr[idx] == 0) {
				idx++;
				continue;
			} 
			arr[idx]--;
			removed++;
		}
		
		//제외되는 사람  부분 제거
		idx = 30;
		removed = 0;
		while(removed < removeCnt) {
			if (arr[idx] == 0) {
				idx--;
				continue;
			} 
			arr[idx]--;
			removed++;
		}
		
		//의견 합 계산
		double difficultySum = 0;
		for(int i = 1; i < 31; i++) {
			difficultySum += (arr[i] * i);
		}
		
		//의견 결과 계산
		int answer = (int)(difficultySum / (n - removeCnt*2) + 0.5);
		
		System.out.println(answer);
	}
}

두 방법 시간 차이 (위 두 번째, 아래  첫 번째)

 

두번째가 훨씬 효율적인 방법임을 알 수 있다.

📍 기억할 것

이런 입력이 큰 수에서는 countingSort가 항상 제일 최고의 시간복잡도를 보여주는 것 같다.