백준 문제 풀이: [18110] solved.ac (JAVA)

백준 문제 풀이: 18110 solved.ac

---

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

문제 설명:

solved.ac 사이트에서 문제 난이도를 결정할 때, 극단적인 값을 제외한 **30% 절사평균**을 사용합니다. 즉, 사용자가 제출한 난이도 중에서 **상위 15%와 하위 15%의 값을 제외**하고 남은 값들의 평균을 계산하여 최종 난이도를 결정합니다.

이때, **제외할 개수와 최종 난이도는 모두 반올림하여 계산**해야 합니다.

---

문제 해결 코드

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

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());
        
        // 예외 처리: 입력이 0일 경우 바로 0 출력 후 종료
        if (N == 0) {
            System.out.println(0);
            return;
        }

        List<Integer> list = new ArrayList<>();
        for (int i = 0; i < N; i++) {
            list.add(Integer.parseInt(br.readLine()));
        }

        // 1. 정렬
        Collections.sort(list);

        // 2. 상/하위 15% 제외 후 평균 구하기
        int removeNum = (int) Math.round(N * 0.15); // 반올림하여 제거할 개수 결정
        int sum = 0, count = 0;

        // 리스트의 중간 값만 합산하여 평균 계산
        for (int i = removeNum; i < N - removeNum; i++) {
            sum += list.get(i);
            count++;
        }

        // 3. 평균 계산 및 반올림하여 출력
        int res = (int) Math.round((double) sum / count);
        System.out.println(res);
    }
}

---

코드 설명

이 코드는 입력된 난이도 의견을 정렬한 후, **상위 15%와 하위 15%의 값을 제외**하고 남은 값들의 평균을 구합니다.

• 핵심 알고리즘: 정렬 후 상/하위 15% 제외 → 남은 값들의 평균 계산.
• 구현 세부사항:
  • 리스트를 정렬하고 극단값을 제외하여 중앙값에 가까운 평균을 구함.
  • `Math.round()`를 사용하여 반올림 처리.
  • `subList()` 없이 리스트를 복사하지 않고 바로 합산하여 성능 최적화.
• 시간 복잡도 분석:
  • 리스트 정렬: O(N log N)
  • 반복문으로 합산: O(N)
  • 총 시간 복잡도: O(N log N)

---

🔴 런타임 에러 발생 원인 및 해결 방법

백준에서는 Main 클래스에서 실행해야 하며, 다른 클래스명(`s18110` 등)을 사용할 경우 런타임 에러(RTE: Java Main class 오류)가 발생합니다.

[런타임 에러 가이드]

💡 해결 방법:

• 클래스명을 **반드시 `Main`으로 수정**해야 합니다.
• 입력이 `0`인 경우 예외 처리를 추가하여 불필요한 연산을 방지합니다.

---

🛠 시간 초과 문제 해결 방법

기존 코드에서는 리스트에서 요소를 하나씩 `remove()`하여 삭제했기 때문에 **O(N²)**의 성능 문제가 발생했습니다.

🚨 기존 문제점

• `ArrayList.remove(index)`는 O(N) 연산이므로, **N번 반복하면 O(N²)의 성능 저하 발생**
• 이로 인해 입력이 클 경우 시간 초과 발생.

✅ 해결 방법

• **`remove()`를 사용하지 않고, 새 리스트를 만들지 않고 바로 평균 계산**
• 반복문을 활용하여 `sum`과 `count`를 직접 계산 (O(N))

🚀 시간 복잡도 개선:

• 기존 코드: O(N log N) + O(N²) = 비효율적
• 개선 코드: O(N log N) + O(N) = 최적화됨

---

💡 예제 입력 및 출력

실제 백준 사이트에는 예제 입력이 있지만, 추가로 예제를 만들어 보았습니다.

📝 입력 예제:

7
1
2
3
4
5
6
100

💡 출력 예제:

4

설명: 상위 15%와 하위 15%를 제외하면 남는 값은 [2, 3, 4, 5, 6]이며, 평균은 4.0이므로 최종 출력값은 4입니다.

---

결론

이 문제에서는 리스트에서 요소를 삭제하는 효율적인 방법이 중요한 포인트였습니다.

• `remove()`를 여러 번 호출하면 O(N²)으로 시간 초과 발생
• 대신 리스트를 **새로 만들지 않고 합산하여 O(N)으로 해결**
• 런타임 에러를 피하려면 클래스명을 `Main`으로 설정해야 함

이제 이 코드를 활용하여 백준에서 AC를 받아보세요! 🚀

다른 접근 방식이나 개선 사항이 있다면 댓글로 공유 부탁드립니다!