백준 5800 성적 통계 JAVA 풀이 (정렬, 구현)

🔗 문제 링크

🔗 https://www.acmicpc.net/problem/5800

---

📌 문제 개요

각 반의 학생 점수가 주어질 때, 반마다 다음 값을 구하는 문제이다.

• 최대 점수 (Max)
• 최소 점수 (Min)
• 인접 점수 간 최대 차이 (Largest gap)

---

📌 접근 방법

이 문제는 정렬을 기반으로 해결

1. 점수를 배열에 저장
2. 오름차순 정렬 수행
3. 정렬된 배열을 기준으로
   • 첫 번째 값 → 최소값
   • 마지막 값 → 최대값
4. 인접한 점수 차이를 계산하며 최대 gap을 찾는다

---

📌 핵심 아이디어

이 문제의 핵심은 Largest gap의 정의

• 단순히 최대값 - 최소값이 아니라
  정렬 후 인접한 점수 간 차이의 최대값

 

예시: 70 71 72 100

정렬 후: 70 71 72 100

gap:

• 71 - 70 = 1
• 72 - 71 = 1
• 100 - 72 = 28

Largest gap = 28

---

📌 전체 코드

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

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

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

        for (int cnt = 1; cnt <= K; cnt++) {
            StringTokenizer st = new StringTokenizer(br.readLine());
            int studentCount = Integer.parseInt(st.nextToken());

            int[] scores = new int[studentCount];
            for (int i = 0; i < studentCount; i++) {
                scores[i] = Integer.parseInt(st.nextToken());
            }

            Arrays.sort(scores);

            int min = scores[0];
            int max = scores[studentCount - 1];
            int maxGap = 0;

            for (int i = 0; i < studentCount - 1; i++) {
                int gap = scores[i + 1] - scores[i];
                maxGap = Math.max(maxGap, gap);
            }

            sb.append("Class ").append(cnt).append("\n");
            sb.append("Max ").append(max)
              .append(", Min ").append(min)
              .append(", Largest gap ").append(maxGap)
              .append("\n");
        }

        System.out.print(sb);
    }
}

---

📌 정리

• 정렬 후 인접 비교가 핵심
• gap 배열을 따로 만들 필요 없이 하나의 변수로 해결 가능
• 시간복잡도: O(N log N)