[Java] BOJ 18110 solved.ac

문제 

문제 링크 https://www.acmicpc.net/problem/18110

• 어떤 문제의 난이도는 그 문제를 푼 사람들이 제출한 난이도 의견을 바탕으로 결정한다.
• 난이도 의견은 그 사용자가 생각한 난이도를 의미하는 정수 하나로 주어진다. solved.ac가 사용자들의 의견을 바탕으로 난이도를 결정하는 방식은 다음과 같다.
  • 아직 아무 의견이 없다면 문제의 난이도는 0으로 결정한다.
  • 의견이 하나 이상 있다면, 문제의 난이도는 모든 사람의 난이도 의견의 30% 절사평균으로 결정한다.
• 절사평균이란 극단적인 값들이 평균을 왜곡하는 것을 막기 위해 가장 큰 값들과 가장 작은 값들을 제외하고 평균을 내는 것을 말한다.
• 30% 절사평균의 경우 위에서 15%, 아래에서 15%를 각각 제외하고 평균을 계산한다.
• 따라서 20명이 투표했다면, 가장 높은 난이도에 투표한 3명과 가장 낮은 난이도에 투표한 3명의 투표는 평균 계산에 반영하지 않는다는 것이다.
• 제외되는 사람의 수는 위, 아래에서 각각 반올림한다. 25명이 투표한 경우 위, 아래에서 각각 3.75명을 제외해야 하는데, 이 경우 반올림해 4명씩을 제외한다.
• 사용자들이 어떤 문제에 제출한 난이도 의견 목록이 주어질 때, solved.ac가 결정한 문제의 난이도를 계산하는 프로그램을 작성하시오.
• 마지막으로, 계산된 평균도 정수로 반올림된다. 절사평균이 16.7이었다면 최종 난이도는 17이 된다.
• 첫 번째 줄에 난이도 의견의 개수 n이 주어진다. (0 ≤ n ≤ 3 × 105)
• 이후 두 번째 줄부터 1 + n번째 줄까지 사용자들이 제출한 난이도 의견 n개가 한 줄에 하나씩 주어진다. 모든 난이도 의견은 1 이상 30 이하이다.
• solved.ac가 계산한 문제의 난이도를 출력한다.

아이디어

• 먼저 배열에 입력받은 값을 저장 후 오름차순으로 정렬하고 그 값을 다시 ArrayDeque에 저장한다.
• 사람수를 기준으로 상위 15%가 몇명인지 계산하기 위해 N * 0.15를 해준후, 반올림을 해준다.
• While문을 통해 제외해야 되는 사람 수가 0이 될때까지 pollFirst, pollLast를 통해 ArrayDeque에서 값을 하나씩 빼준 후, 제외해야되는 사람 수 - 1을 해준다.
• 다 빼준 후, ArrayDeque에 남은 수를 다 더해서 인원수대로 나눠 평균을 구해준다. 

겪은 시행착오

• X

ArrayDeque를 활용해서 잘 풀 수 있어서 뿌듯했다!

코드

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

public class BOJ18110 {
    public static void main(String[] args) throws Exception{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        int N = Integer.parseInt(br.readLine());

        // 점수 입력 받음
        int score[] = new int[N];
        // 정렬한 점수를 넣을 Deque
        ArrayDeque<Integer> solved = new ArrayDeque<>();

        // 점수를 입렫받음
        for(int i = 0; i < N; i++){
            int n = Integer.parseInt(br.readLine());

            score[i] = n;
        }

        // 점수를 정렬
        Arrays.sort(score);

        // 정렬한 점수를 Deque에 저장
        for(int i = 0; i < N; i++){
            solved.addLast(score[i]);
        }

        // 위 아래로 몇명 제외해야되는지 퍼센테이지 계산
        int cnt = (int)Math.round(N * 0.15);

        // 제외해야되는 사람이 0이 될 때까지 반복
        while(true){
            if(cnt == 0){
                break;
            }

            // 맨 위와 맨 밑의 점수를 제거
            solved.pollFirst();
            solved.pollLast();

            cnt = cnt - 1;
        }

        // 결과값 저장
        float result = 0;

        for(int i : solved){
            result = result + i;
        }

        // 평균값을 구함
        result = Math.round(result / solved.size());

        // int로 변환
        int avg = (int)result;

        System.out.println(avg);
    }
}