📌 문제
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가 계산한 문제의 난이도를 출력한다.
예시
5
1
5
5
7
86
5명의 15%는 0.75명으로, 이를 반올림하면 1명이다. 따라서 solved.ac는 가장 높은 난이도 의견과 가장 낮은 난이도 의견을 하나씩 제외하고, {5, 5, 7}에 대한 평균으로 문제 난이도를 결정한다.
👀 문제 해석
solved.ac에서 문제의 난이도를 결정하는 방식을 구현하는 문제이다. 핵심은 30% 절사평균을 계산하는 것인데, 크게 세 가지 단계로 나뉜다.
첫째, 아무 의견이 없다면 난이도는 0으로 결정한다.
둘째, 의견이 하나 이상 있다면 30% 절사평균을 계산한다. 이는 극단적인 값들이 평균을 왜곡하는 것을 막기 위해 상위 15%와 하위 15%를 제외하고 평균을 구하는 방식이다.
셋째, 제외되는 사람의 수는 위아래에서 각각 반올림한다. 예를 들어 25명이 투표한 경우 15%인 3.75명을 반올림하여 4명씩을 제외한다.
마지막으로 계산된 평균도 정수로 반올림하여 최종 난이도를 결정한다.
입력으로는 난이도 의견의 개수 n(0 ≤ n ≤ 3×10⁵)이 주어지고, 이후 각 사용자가 제출한 난이도 의견(1~30)이 한 줄씩 주어진다.
문제의 핵심 포인트는 다음과 같다.
- 의견이 많을 수 있으므로(최대 30만 개) 효율적인 처리가 필요하다
- 30% 절사평균 계산 시 상위/하위 15%씩 제외해야 한다
- 제외 인원 수는 반올림으로 결정하며, 계산된 평균도 반올림한다
- 난이도는 1~30 범위로 제한되어 있다는 특성을 활용할 수 있다
🔎 접근
시간 복잡도 고민
처음 문제를 보자마자 떠오른 것은 "어떻게 하면 효율적으로 상위/하위 15%를 제거할 수 있을까?"였다.
가장 직관적인 방법은 정렬을 사용하는 것이다. 모든 의견을 배열에 담고 정렬한 후, 앞뒤에서 필요한 만큼 제거하면 된다.
방법 1: 정렬 사용
- 시간복잡도: O(n log n)
- 공간복잡도: O(n)
- 구현이 간단하고 직관적
// 정렬 방식 예시
int[] opinions = new int[n];
for (int i = 0; i < n; i++) {
opinions[i] = Integer.parseInt(br.readLine());
}
Arrays.sort(opinions);
int trim = (int) Math.round(n * 0.15);
int sum = 0;
for (int i = trim; i < n - trim; i++) {
sum += opinions[i];
}
하지만 n이 최대 30만이므로 O(n log n)도 충분히 빠르긴 하다. 그런데 문제를 다시 들여다보니 결정적 단서가 숨어 있었다.
"모든 난이도 의견은 1 이상 30 이하"
이 조건이 게임 체인저였다. 값의 범위가 고정되어 있다면 정렬할 필요 없이 카운팅만으로도 해결할 수 있다는 아이디어가 떠올랐다.
더 나은 접근: 카운팅 정렬
방법 2: 카운팅 배열 사용
- 시간복잡도: O(n + k) where k = 30 (상수)
- 공간복잡도: O(k) = O(30) (상수)
- 값의 범위가 작을 때 매우 효율적
핵심 아이디어는 다음과 같다.
- 크기 31인 카운팅 배열을 만든다 (인덱스 1~30 사용)
- 각 의견을 입력받을 때마다 해당 인덱스의 카운트를 증가시킨다
- 하위 15%를 제거할 때는 1부터 순차적으로 카운트를 차감한다
- 상위 15%를 제거할 때는 30부터 역순으로 카운트를 차감한다
- 남은 카운트들로 가중평균을 계산한다
int[] cnt = new int[31]; // 1~30 사용
for (int i = 0; i < n; i++) {
int v = Integer.parseInt(br.readLine());
cnt[v]++;
}
int trim = (int) Math.round(n * 0.15);
// 하위 15% 제거 (1부터 시작)
int skipLow = trim;
for (int v = 1; v <= 30 && skipLow > 0; v++) {
int use = Math.min(skipLow, cnt[v]);
cnt[v] -= use;
skipLow -= use;
}
// 상위 15% 제거 (30부터 시작)
int skipHigh = trim;
for (int v = 30; v >= 1 && skipHigh > 0; v--) {
int use = Math.min(skipHigh, cnt[v]);
cnt[v] -= use;
skipHigh -= use;
}
왜 카운팅 방식이 더 좋은가?
성능 비교:
- 정렬 방식: O(n log n) = O(300,000 × log 300,000) ≈ O(300,000 × 18) ≈ 5,400,000 연산
- 카운팅 방식: O(n + 30) = O(300,000 + 30) = 300,030 연산
카운팅 방식이 약 18배 빠르다!
메모리 사용량:
- 정렬 방식: O(n) = 최대 1.2MB (int 배열 기준)
- 카운팅 방식: O(30) = 120 바이트
메모리도 훨씬 적게 사용한다.
카운팅 정렬의 시간 복잡도 계산?
카운팅 방식의 시간 복잡도는 앞서 O(N + K) 라고 설명했다. 어떻게 이게 가능한 것일까?
- 카운팅 배열 초기화 (O(K)):
- 크기가 K인 카운팅 배열 cnt를 생성하고 0으로 초기화합니다. 이 과정은 배열의 크기 K에 비례하는 시간이 걸린다.
- int[] cnt = new int[31]; // K = 31 (0~30)
- 입력 데이터의 빈도수 계산 (O(N)):
- N개의 입력 데이터를 하나씩 읽으면서, 각 데이터 값에 해당하는 cnt 배열의 인덱스 값을 1씩 증가시킨다. 각 데이터를 한 번씩만 접근하므로 N에 비례하는 시간이 걸린다.
- for (int i = 0; i < n; i++) { cnt[opinions[i]]++; }
- 절사 및 평균 계산을 위한 배열 순회 (O(K)):
- 하위/상위 의견을 제외하고 남은 의견으로 평균을 계산하기 위해 cnt 배열을 순회한다. 이 과정은 cnt 배열의 크기 K에 비례하는 시간이 걸린다. (하위 제외 루프, 상위 제외 루프, 최종 합산 루프 모두 최대 K번 반복)
- for (int v = 1; v <= 30 ...)
- for (int v = 30; v >= 1 ...)
- for (int v = 1; v <= 30 ...) (평균 계산 시)
이 세 단계를 모두 합치면 총 시간 복잡도는 O(K) + O(N) + O(K) = O(N + 2K) 가 된다. 빅오 표기법에 따라 최종적으로 O(N + K) 이 된다.
<svg width="700" height="450" xmlns="http://www.w3.org/2000/svg">
<style>
.title { font-family: Arial, sans-serif; font-size: 18px; font-weight: bold; text-anchor: middle; }
.step-title { font-family: Arial, sans-serif; font-size: 14px; font-weight: bold; }
.desc { font-family: Arial, sans-serif; font-size: 12px; }
.complexity { font-family: 'Courier New', Courier, monospace; font-size: 13px; fill: #e74c3c; font-weight: bold;}
.box { stroke: #3498db; stroke-width: 1.5; fill: #ecf0f1; }
.arrow { stroke: #2c3e50; stroke-width: 2; marker-end: url(#arrowhead); }
.highlight-N { fill: #2ecc71; }
.highlight-K { fill: #f39c12; }
</style>
<defs>
<marker id="arrowhead" markerWidth="10" markerHeight="7" refX="0" refY="3.5" orient="auto">
<polygon points="0 0, 10 3.5, 0 7" fill="#2c3e50"/>
</marker>
</defs>
<text x="350" y="30" class="title">카운팅 방식 시간 복잡도 분석: O(N + K)</text>
<rect x="50" y="60" width="150" height="100" class="box"/>
<text x="125" y="80" text-anchor="middle" class="step-title">1. 배열 초기화</text>
<text x="125" y="105" text-anchor="middle" class="desc">크기 K (31) 배열 생성</text>
<text x="125" y="125" text-anchor="middle" class="desc">& 0으로 채우기</text>
<text x="125" y="145" text-anchor="middle" class="complexity">O(K)</text>
<line x1="200" y1="110" x2="240" y2="110" class="arrow"/>
<rect x="250" y="60" width="200" height="100" class="box"/>
<text x="350" y="80" text-anchor="middle" class="step-title">2. 빈도수 계산</text>
<text x="350" y="105" text-anchor="middle" class="desc">N개 의견 입력받아</text>
<text x="350" y="125" text-anchor="middle" class="desc">카운트 배열 업데이트</text>
<text x="350" y="145" text-anchor="middle" class="complexity">O(N)</text>
<line x1="450" y1="110" x2="490" y2="110" class="arrow"/>
<rect x="500" y="60" width="150" height="100" class="box"/>
<text x="575" y="80" text-anchor="middle" class="step-title">3. 배열 순회</text>
<text x="575" y="105" text-anchor="middle" class="desc">절사 및 평균 계산 위해</text>
<text x="575" y="125" text-anchor="middle" class="desc">카운트 배열 순회</text>
<text x="575" y="145" text-anchor="middle" class="complexity">O(K)</text>
<rect x="50" y="200" width="600" height="150" class="box" fill="#f9f9f9"/>
<text x="350" y="225" text-anchor="middle" class="step-title">전체 시간 복잡도</text>
<text x="180" y="260" class="desc">단계 1 (배열 초기화):</text>
<text x="350" y="260" class="complexity">O(K)</text>
<text x="180" y="285" class="desc">단계 2 (빈도수 계산):</text>
<text x="350" y="285" class="complexity">O(N)</text>
<text x="180" y="310" class="desc">단계 3 (배열 순회):</text>
<text x="350" y="310" class="complexity">O(K)</text>
<line x1="180" y1="320" x2="400" y2="320" stroke="#7f8c8d" stroke-width="1"/>
<text x="180" y="340" class="desc" font-weight="bold">총합:</text>
<text x="350" y="340" class="complexity" fill="#2980b9">O(N + K + K) = O(N + 2K) → O(N + K)</text>
<text x="350" y="380" text-anchor="middle" class="desc">
N: 입력 의견의 수 (예: 300,000)
</text>
<text x="350" y="400" text-anchor="middle" class="desc">
K: 난이도 의견의 범위 (예: 30)
</text>
<text x="350" y="420" text-anchor="middle" class="desc" font-style="italic">
빅오 표기법에 따라 → O(N)
</text>
</svg>
우선순위 큐는 어떨까?
혹시나 해서 우선순위 큐 2개를 사용하는 방법도 고려해봤다.
방법 3: 우선순위 큐 활용
- MinHeap으로 상위 15% 관리
- MaxHeap으로 하위 15% 관리
- 시간복잡도: O(n log k) where k = 제외할 개수
PriorityQueue<Integer> minHeap = new PriorityQueue<>(); // 상위 15%
PriorityQueue<Integer> maxHeap = new PriorityQueue<>(Collections.reverseOrder()); // 하위 15%
// 각 의견을 두 힙에서 관리하며 크기 제한
이 방법도 나쁘지는 않아보이는데 계산은 어떨까?
- 모든 n개의 항목을 우선순위 큐에 넣는 데 O(n log n).
- k개의 항목을 추출하는 데 O(k log n).
만약 남은 항목으로 다시 힙을 만들거나 복잡한 처리를 한다면 추가 시간이 소요될 것이다.
우선순위 큐를 사용하면 정렬과 유사한 시간 복잡도를 갖게 되거나, 로직이 더 복잡해질 것으로 보인다.
상위/하위 k개를 "제외"하는 작업은 정렬된 배열에서 양 끝을 잘라내는 것보다 우선순위 큐로는 다소 번거로울 수 있다. 예를 들어, 가장 작은 k개와 가장 큰 k개를 모두 효율적으로 제거하려면 두 개의 힙을 운영하거나, 하나의 힙에서 k개를 제거한 후 남은 것들로 다시 처리하는 과정이 필요하다. 차라리 그럴 바엔 정렬 후 슬라이싱하는 것이 더 간단해 보인다.
따라서, 값의 범위가 제한된 이 문제에서는 카운팅 방식보다 복잡하고 느리다.
최종 선택: 카운팅 배열
결국 카운팅 배열 방식을 선택했다.
- 압도적인 성능: O(n) vs O(n log n)
- 메모리 효율성: 상수 공간 vs 선형 공간
- 구현의 명확성: 제거 과정이 직관적
- 문제 특성 활용: 1~30 범위 제한을 완벽히 활용
결국 범위가 제한되어 있다는 점이 압도적인 힌트다.
참고로, 비교 기반 정렬 알고리즘의 시간 복잡도 하한은 O(n log n) 이다. 그러나 현재 문제처럼 입력 데이터의 값의 범위가 제한적이고 정수형일 때는 계수 정렬(또는 기수 정렬(Radix Sort))과 같은 비교 기반이 아닌 정렬 알고리즘을 사용하여 선형 시간 O(n+k), 결론적으로 O(n)의 성능을 얻을 수 있다.
이 문제의 경우 첫번째 아이디어인 정렬 방식, 즉 sort를 사용해도 풀린다. 그러나 만약 데이터 셋이 추가 되면 제한시간 초과로 통과하지 못할 것이다.
난이도 의견이 1에서 30 사이의 정수로 주어진다는 것이 힌트인 이유다.
💡 풀이 코드
이제 앞서 정리한 카운팅 배열 아이디어를 자바로 구현해보자.
핵심은 정렬 없이 카운팅만으로 상위/하위 15%를 제거하고 절사평균을 계산하는 것이다.
🔖 코드 준비 및 입력 받기
우선, 백준 포맷에 따라 입력을 받아야 한다. 문제에서 주어진 예시를 살펴보면:
5
1
5
5
7
8
여기서 n = 5이며, 난이도 의견은 {1, 5, 5, 7, 8}이다.
초기화 및 입력 과정에서 각 의견의 빈도수를 카운팅 배열에 저장한다.
| 난이도 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | ... | 30 |
| 개수 | 1 | 0 | 0 | 0 | 2 | 0 | 1 | 1 | ... | 0 |
실제 코드의 입력 처리 부분을 살펴보면
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
int n = Integer.parseInt(br.readLine().trim());
if (n == 0) {
System.out.println(0);
return;
}
int[] cnt = new int[31]; // 인덱스 1~30 사용
for (int i = 0; i < n; i++) {
int v = Integer.parseInt(br.readLine().trim());
cnt[v]++;
}
이렇게 하여 각 난이도별 의견 개수가 cnt 배열에 저장된다.
🚩 절사평균 계산 메커니즘
절사평균 계산은 세 단계로 진행된다.
- 제외할 개수 계산: trim = round(n * 0.15)
- 하위 15% 제거: 1부터 시작해서 trim개만큼 제거
- 상위 15% 제거: 30부터 시작해서 trim개만큼 제거
예시로 n=5인 경우를 살펴보면 다음과 같다.
- trim = round(5 * 0.15) = round(0.75) = 1
- 하위 1개, 상위 1개를 제거해야 함
하위 15% 제거 과정
int trim = (int) Math.round(n * 0.15);
int skipLow = trim;
for (int v = 1; v <= 30 && skipLow > 0; v++) {
int use = Math.min(skipLow, cnt[v]);
cnt[v] -= use;
skipLow -= use;
}
이 과정을 시각화하면 다음과 같다.
| 단계 | 현재 v | cnt[v] | skipLow | use | 제거 후 cnt[v] | 남은 skipLow |
| 시작 | - | - | 1 | - | - | 1 |
| 1 | 1 | 1 | 1 | min(1,1)=1 | 0 | 0 |
난이도 1인 의견 1개가 제거되어 하위 15% 제거 완료.
<svg width="650" height="450" xmlns="http://www.w3.org/2000/svg">
<style>
.title { font-family: 'Malgun Gothic', Arial, sans-serif; font-size: 18px; font-weight: bold; text-anchor: middle; }
.step-title { font-family: 'Malgun Gothic', Arial, sans-serif; font-size: 14px; font-weight: bold; }
.desc { font-family: 'Malgun Gothic', Arial, sans-serif; font-size: 12px; }
.code { font-family: 'Courier New', Courier, monospace; font-size: 11px; fill: #2c3e50; }
.var-highlight { font-weight: bold; fill: #c0392b; }
.array-box { stroke: #7f8c8d; stroke-width: 1; fill: #ecf0f1; rx:3; ry:3; }
.array-cell { stroke: #bdc3c7; stroke-width: 1; fill: #ffffff; }
.array-index { font-size: 10px; text-anchor: middle; fill: #34495e; }
.array-value { font-size: 12px; text-anchor: middle; font-weight: bold; }
.highlight-cell { fill: #f1c40f; }
.strikethrough { text-decoration: line-through; fill: #95a5a6; }
.arrow { stroke: #2980b9; stroke-width: 2; marker-end: url(#arrowhead); fill: none; }
.loop-box { stroke: #16a085; stroke-width: 1.5; fill: #e8f6f3; rx:5; ry:5;}
.status-box { stroke: #8e44ad; stroke-width: 1.5; fill: #f4ecf7; rx:5; ry:5;}
</style>
<defs>
<marker id="arrowhead" markerWidth="8" markerHeight="6" refX="7" refY="3" orient="auto">
<polygon points="0 0, 8 3, 0 6" fill="#2980b9"/>
</marker>
</defs>
<text x="30" y="60" class="step-title">1. 초기 상태 (예제 1 기준)</text>
<text x="30" y="80" class="desc"><tspan class="code">n = 5</tspan>, 의견: 1, 5, 5, 7, 8</text>
<text x="30" y="100" class="desc"><tspan class="code">trim = (int) Math.round(5 * 0.15) = 1</tspan></text>
<text x="30" y="120" class="desc"><tspan class="code">skipLow = trim = </tspan><tspan class="var-highlight">1</tspan></text>
<text x="30" y="150" class="desc">cnt 배열 (일부):</text>
<rect x="30" y="160" width="360" height="50" class="array-box"/>
<text x="60" y="175" class="array-index">cnt[1]</text><rect x="35" y="180" width="50" height="25" class="array-cell"/><text x="60" y="197" class="array-value">1</text>
<text x="110" y="175" class="array-index">cnt[2]</text><rect x="85" y="180" width="50" height="25" class="array-cell"/><text x="110" y="197" class="array-value">0</text>
<text x="160" y="175" class="array-index">cnt[3]</text><rect x="135" y="180" width="50" height="25" class="array-cell"/><text x="160" y="197" class="array-value">0</text>
<text x="210" y="175" class="array-index">cnt[4]</text><rect x="185" y="180" width="50" height="25" class="array-cell"/><text x="210" y="197" class="array-value">0</text>
<text x="260" y="175" class="array-index">cnt[5]</text><rect x="235" y="180" width="50" height="25" class="array-cell"/><text x="260" y="197" class="array-value">2</text>
<text x="310" y="175" class="array-index">...</text>
<text x="360" y="175" class="array-index">cnt[8]</text><rect x="335" y="180" width="50" height="25" class="array-cell"/><text x="360" y="197" class="array-value">1</text>
<rect x="30" y="235" width="590" height="140" class="loop-box"/>
<text x="40" y="250" class="step-title">2. for 루프 실행: <tspan class="code">for (int v = 1; v <= 30 && skipLow > 0; v++)</tspan></text>
<text x="50" y="275" class="desc"><tspan fill="#16a085" font-weight="bold">현재 v = 1</tspan> (skipLow = <tspan class="var-highlight">1</tspan> > 0 이므로 루프 진행)</text>
<text x="60" y="295" class="code">int use = Math.min(skipLow, cnt[v]);</text>
<text x="70" y="310" class="desc">↳ use = Math.min(<tspan class="var-highlight">1</tspan>, cnt[<tspan class="var-highlight">1</tspan>]) = Math.min(<tspan class="var-highlight">1</tspan>, <tspan class="var-highlight">1</tspan>) = <tspan class="var-highlight">1</tspan></text>
<text x="60" y="325" class="code">cnt[v] -= use;</text>
<text x="70" y="340" class="desc">↳ cnt[<tspan class="var-highlight">1</tspan>] = <tspan class="var-highlight">1</tspan> - <tspan class="var-highlight">1</tspan> = <tspan class="var-highlight">0</tspan></text>
<text x="60" y="355" class="code">skipLow -= use;</text>
<text x="70" y="370" class="desc">↳ skipLow = <tspan class="var-highlight">1</tspan> - <tspan class="var-highlight">1</tspan> = <tspan class="var-highlight">0</tspan></text>
<rect x="400" y="60" width="220" height="150" class="status-box"/>
<text x="410" y="80" class="step-title">3. 루프 상태 변화</text>
<text x="410" y="100" class="desc">변경된 <tspan class="code">cnt[1]</tspan>: <tspan class="var-highlight">0</tspan></text>
<rect x="405" y="110" width="50" height="25" class="array-cell highlight-cell"/>
<text x="430" y="127" class="array-value"><tspan class="bold"> 1 </tspan> → 0</text>
<text x="410" y="150" class="desc">변경된 <tspan class="code">skipLow</tspan>: <tspan class="var-highlight">0</tspan></text>
<text x="410" y="170" class="desc">다음 반복 시 <tspan class="code">(skipLow > 0)</tspan> 조건이 false.</text>
<text x="410" y="190" class="desc"><tspan fill="#e74c3c" font-weight="bold">⇒ 하위 의견 제외 루프 종료.</tspan></text>
<path d="M 210 210 Q 265 220, 280 235" class="arrow"/> <path d="M 290 370 Q 390 300, 480 215" class="arrow"/> <text x="30" y="400" class="step-title">4. 최종 결과</text>
<text x="30" y="420" class="desc">난이도 1인 의견 1개가 <tspan class="code">cnt</tspan> 배열에서 제거됨</text>
<text x="30" y="435" class="desc"><tspan class="code">skipLow</tspan>가 0이 되어 하위 15% 제외가 완료됨</text>
</svg>
상위 15% 제거 과정
위에서 작성한 하위 15%를 반대로 해주면 상위 15%가 된다.
int skipHigh = trim;
for (int v = 30; v >= 1 && skipHigh > 0; v--) {
int use = Math.min(skipHigh, cnt[v]);
cnt[v] -= use;
skipHigh -= use;
}
| 단계 | 현재 v | cnt[v] | skipHigh | use | 제거 후 cnt[v] | 남은 skipHigh |
| 시작 | - | - | 1 | - | - | 1 |
| ... | 30~9 | 0 | 1 | 0 | 0 | 1 |
| 8 | 8 | 1 | 1 | min(1,1)=1 | 0 | 0 |
난이도 8인 의견 1개가 제거되어 상위 15% 제거 완료.
최종 평균 계산
제거 후 남은 의견들로 가중평균을 계산한다.
long sum = 0;
int remain = n - trim - trim; // 5 - 1 - 1 = 3
for (int v = 1; v <= 30; v++) {
sum += (long) v * cnt[v];
}
System.out.println((int) Math.round((double) sum / remain));
남은 의견: {5, 5, 7} → 평균 = (5×2 + 7×1) / 3 = 17/3 = 5.67 → round(5.67) = 6
🎯 최적화 포인트
- 오버플로우 방지: sum을 long 타입으로 선언
- 최악의 경우: 30 × 300,000 = 9,000,000 (int 범위 내)
- 하지만 안전을 위해 long 사용
- 효율적인 제거 로직: Math.min(skipLow, cnt[v])
- 현재 값의 개수보다 많이 제거하려 할 때 적절히 조절
- 여러 값에 걸쳐 제거할 수 있도록 유연하게 처리
- 부동소수점 정확성: Math.round() 사용
- 단순한 (int)(x + 0.5) 대신 정확한 반올림 함수 사용
- 단순한 (int)(x + 0.5) 대신 정확한 반올림 함수 사용
🚀 최종 제출 코드
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
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().trim());
if (n == 0) {
System.out.println(0);
return;
}
int[] cnt = new int[31];
for (int i = 0; i < n; i++) {
int v = Integer.parseInt(br.readLine().trim());
cnt[v]++;
}
int trim = (int) Math.round(n * 0.15);
int skipLow = trim;
int skipHigh = trim;
// 하위 15% 제거
for (int v = 1; v <= 30 && skipLow > 0; v++) {
int use = Math.min(skipLow, cnt[v]);
cnt[v] -= use;
skipLow -= use;
}
// 상위 15% 제거
for (int v = 30; v >= 1 && skipHigh > 0; v--) {
int use = Math.min(skipHigh, cnt[v]);
cnt[v] -= use;
skipHigh -= use;
}
// 절사평균 계산
long sum = 0;
int remain = n - trim - trim;
for (int v = 1; v <= 30; v++) {
sum += (long) v * cnt[v];
}
System.out.println((int) Math.round((double) sum / remain));
}
}
'알고리즘 > 백준' 카테고리의 다른 글
| [BOJ 백준] 1759 암호만들기 (백트래킹 자바 풀이) (0) | 2025.05.25 |
|---|---|
| [BOJ 백준] 지름길 (자바 풀이, 그리디, 다익스트라) (0) | 2025.05.17 |
| [BOJ] 백준 4195 친구 네트워크 (유니온 파인드 최적화 자바 풀이) (0) | 2025.05.04 |
| 백준 5639 이진 검색 트리 (JAVA 자바 풀이) (0) | 2024.11.23 |
| [백준] 기념품 (자바 풀이) (4) | 2024.10.12 |
