[백준] 18110 solved.ac

lkdcode·2023년 9월 20일

Java algorithm 백준

Algorithm

목록 보기

42/47

[18110] solved.ac

문제 분석

예제 1로 분석한다.

5 <- 난이도 갯수
1 <- 첫번째 난이도
5 <- 두번째 난이도
5 <- 세번째 난이도
7 <- 네번째 난이도
8 <- 마지막 난이도

첫 번째 줄에 난이도 갯수 n이 주어지고 이어서 n개 만큼 난이도가 주어진다.
난이도들의 절사평균(30%) 을 구하여 리턴하는 문제.

풀이 과정

🎯 입력 조건을 잘 보자. 0이 주어진다.

0은 제외해야한다.
입력받는 로직을 돌렸을 때 오류가 날 수도 있다.

0인 경우를 제외시키는 코드를 추가하자.

if (size == 0) {
    System.out.println("0");
    return;
}

🎯 배열에 저장, 정렬 후 범위로 계산해보자.

난이도들을 입력받아 배열에 저장하자.

int[] list = new int[size];

for (int i = 0; i < size; i++) {
    list[i] = Integer.parseInt(br.readLine());
}

배열을 정렬하자.

Arrays.sort(list);

예제 1을 기준으로 절사 평균(30%)은 5 * 0.15 = 0.75 에서 반올림 된 1 이다.

int trimmedAverage = (int) Math.round(size * 0.15);

예제 1을 기준으로 입력받은 배열은 {1, 5, 5, 7, 8} 이 들어있다.
여기서 우리가 필요한 값은 5, 5, 7 이다. 인덱스 로 보자면 [1], [2], [3] 이다.
그렇다면 시작 인덱스 와 마지막 인덱스 만 알면 for 문을 돌릴 수 있다.

마지막 인덱스는 주어질 n(size) 에서 한 쪽의 절사 평균 을 뺀 값이 된다.
예제에선 n(size) 은 5 가 되고 trimmedAverage 는 1 이 된다

int trimmedSize = size - trimmedAverage; // 5 - 1 = 4

시작 인덱스는 절사 평균(trimmedAverage)이 된다.

위의 로직으로 정렬된 배열에 접근하게 되면 답을 바로 구할 수 있다.
double result = 0; 로 선언한 이유는 int 타입으로 나누기를 하면 정확한 값이 안 나온다.

double result = 0;

for (int i = trimmedAverage; i < trimmedSize; i++) {
    result += list[i];
}

🎯 결과 값도 반올림 하자.

double result = 0; 가 double 타입이라 나누기 연산이 정확히 될 것이고
Math.round() 메서드로 반올림해주면 된다.

System.out.println(Math.round(result / (trimmedSize - trimmedAverage)));

나의 생각

처음에 우선순위 큐로 구현하여 문제를 풀었다가 시간 복잡도가 그렇게 좋아보이진 않아서
똑같은 로직을 배열로 바꿔서 구현해봤다.
배열이 더 빨랐는데 랜덤 엑세스(O(1))가 가능하기 때문에 더 빠른 것 같다.

코드

package baekjooncompletion;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.PriorityQueue;
import java.util.concurrent.PriorityBlockingQueue;

public class BaekJoon18110 {
    private static final BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

    public static void main(String[] args) throws IOException {
        int size = Integer.parseInt(br.readLine());

        if (size == 0) {
            System.out.println("0");
            return;
        }

        int[] list = new int[size];

        for (int i = 0; i < size; i++) {
            list[i] = Integer.parseInt(br.readLine());
        }

        Arrays.sort(list);

        int trimmedAverage = (int) Math.round(size * 0.15);
        int trimmedSize = size - trimmedAverage;

        double result = 0;

        for (int i = trimmedAverage; i < trimmedSize; i++) {
            result += list[i];
        }

        System.out.println(Math.round(result / (trimmedSize - trimmedAverage)));

    }

}