[Baekjoon] 18110 solved.ac - JAVA

문제

solved.ac는 Sogang ICPC Team 학회원들의 알고리즘 공부에 도움을 주고자 만든 서비스이다. 지금은 서강대뿐만 아니라 수많은 사람들이 solved.ac의 도움을 받아 알고리즘 공부를 하고 있다.

 

ICPC Team은 백준 온라인 저지에서 문제풀이를 연습하는데, 백준 온라인 저지의 문제들에는 난이도 표기가 없어서, 지금까지는 다양한 문제를 풀어 보고 싶더라도 난이도를 가늠하기 어려워 무슨 문제를 풀어야 할지 판단하기 곤란했기 때문에 solved.ac가 만들어졌다. solved.ac가 생긴 이후 전국에서 200명 이상의 기여자 분들께서 소중한 난이도 의견을 공유해 주셨고, 지금은 약 7,000문제에 난이도 표기가 붙게 되었다.

어떤 문제의 난이도는 그 문제를 푼 사람들이 제출한 난이도 의견을 바탕으로 결정한다. 난이도 의견은 그 사용자가 생각한 난이도를 의미하는 정수 하나로 주어진다. solved.ac가 사용자들의 의견을 바탕으로 난이도를 결정하는 방식은 다음과 같다.

• 아직 아무 의견이 없다면 문제의 난이도는 0으로 결정한다.
• 의견이 하나 이상 있다면, 문제의 난이도는 모든 사람의 난이도 의견의 30% 절사평균으로 결정한다.

절사평균이란 극단적인 값들이 평균을 왜곡하는 것을 막기 위해 가장 큰 값들과 가장 작은 값들을 제외하고 평균을 내는 것을 말한다. 30% 절사평균의 경우 위에서 15%, 아래에서 15%를 각각 제외하고 평균을 계산한다. 따라서 20명이 투표했다면, 가장 높은 난이도에 투표한 3명과 가장 낮은 난이도에 투표한 3명의 투표는 평균 계산에 반영하지 않는다는 것이다.

제외되는 사람의 수는 위, 아래에서 각각 반올림한다. 25명이 투표한 경우 위, 아래에서 각각 3.75명을 제외해야 하는데, 이 경우 반올림해 4명씩을 제외한다.

마지막으로, 계산된 평균도 정수로 반올림된다. 절사평균이 16.7이었다면 최종 난이도는 17이 된다.

사용자들이 어떤 문제에 제출한 난이도 의견 목록이 주어질 때, solved.ac가 결정한 문제의 난이도를 계산하는 프로그램을 작성하시오.

입력

첫 번째 줄에 난이도 의견의 개수 n이 주어진다. (0 ≤ n ≤ 3 × 105)

이후 두 번째 줄부터 1 + n번째 줄까지 사용자들이 제출한 난이도 의견 n개가 한 줄에 하나씩 주어진다. 모든 난이도 의견은 1 이상 30 이하이다.

출력

solved.ac가 계산한 문제의 난이도를 출력한다.

예제 입력 1 

5
1
5
5
7
8

예제 출력 1 

6

5명의 15%는 0.75명으로, 이를 반올림하면 1명이다. 따라서 solved.ac는 가장 높은 난이도 의견과 가장 낮은 난이도 의견을 하나씩 제외하고, {5, 5, 7}에 대한 평균으로 문제 난이도를 결정한다.

예제 입력 2 

10
1
13
12
15
3
16
13
12
14
15

예제 출력 2 

13

 

---

📝 제출답안

 

❌ 오답

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Collections;

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        ArrayList<Integer> scores = new ArrayList<>();

        int n = Integer.parseInt(br.readLine());
        for (int i = 0; i < n; i++) {
            scores.add(Integer.parseInt(br.readLine()));
        }
        Collections.sort(scores);

        int per = (int) Math.round(n*0.15);
        for (int i = 0; i < per; i++) {
            scores.remove(0);
            scores.remove(scores.size() - 1);
        }
        
        int sum = 0;
        for (int i = 0; i < scores.size(); i++) {
            sum += scores.get(i);
        }

        int res = Math.round((float) sum /scores.size());
        System.out.println(res);
    }
}

 

⭕ 정답

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collections;

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

        int n = Integer.parseInt(br.readLine());
        int[] scores = new int[n];
        for (int i = 0; i < n; i++) {
            scores[i] = Integer.parseInt(br.readLine());
        }
        Arrays.sort(scores);

        int per = (int) Math.round(n*0.15);
        int sum = 0;
        for (int i = per; i < scores.length - per; i++) {
            sum += scores[i];
        }

        int res = Math.round((float) sum /(n-2*per));
        System.out.println(res);
    }
}

 

 

처음에 작성한 코드에서 시간 초과가 떴다.

 

그 이유는 ArrayList의 remove() 메서드가 요소를 제거한 뒤 남은 요소를 모두 한 칸씩 이동시키는 데 발생하는 비용이 O(n) 시간이고, 여러 번 호출할 경우 O(n^2)의 시간 복잡도를 가지기 때문이다. Collections.sort에서도 O(nlogn) 만큼의 시간 복잡도가 발생한다.

 

이러한 이유 때문에 양 끝 요소를 제거하는 방법으로 ArrayList 대신, 인덱스 기반 접근을 할 수 있도록 배열로 변경해주었다.

 

ArrayList 대신 int[] 배열로 접근하여 메모리 이동 오버헤드를 줄이고자 하였다. remove() 연산을 제거하고 유효한 범위 내에서 순회하며 필요한 부분만 합산하도록 로직을 변경해주었고,

Arrays.sort()는 그대로 O(nlogn) 시간 복잡도를 가진다.

 

이에 따라 입력 크기가 커지더라도 O(nlogn)에 정렬 작업을 처리하고, 단일 루프 O(n)으로 결과를 계산하므로 시간 초과 발생을 없애고 문제를 해결하였다.

---

🪄 Array vs. ArrayList

배열

• 크기 : 정적. 생성 시 크기를 지정해야 하고, 변경이 불가능함.
• 유연성 :동일한 데이터 타입의 요소만 저장 가능하고, 배열의 크기나 요소를 직접 관리해야 함.
• 성능 : 빠름. 크기가 고정되어 있고, 요소 접근 및 수정을 상수 시간 O(1) 내에 가능. 불필요한 오버헤드 없음.

 

ArrayList

• 크기 : 동적. 요소 추가 및 제거 시 내부적으로 배열을 재할당하여 크기 관리가 가능함.
• 유연성 :제네릭으로 다양한 데이터 타입 저장 가능. 동적 크기 조정으로 개발자 관리 작업이 줄어듦.
• 성능 : 약간 느림. 요소 추가, 삭제 시 배열 크기를 조정하거나 요소를 이동해야 하므로 추가적인 오버헤드 발생. → 크기 조정 시 새로운 배열을 생성하고 기존 데이터를 복사하므로 비효율적 : O(n)

 

제출현황