BOJ 2587 - 대표값2

https://www.acmicpc.net/problem/2587

2587번: 대표값2

---

이번 문제는 counting sort 방법으로 해결해 시간복잡도는 O(n) 으로 해결하였다.

 

문제에 숫자는 5개가 주어진다고 명시되어 있으므로 중앙값은 항상 3이기 때문에, counting sort 배열 출력 시 3번째 값이 중앙값이 된다.

 

 

 

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));
        StringBuilder sb = new StringBuilder();
        int[] arr = new int[101];
        int sum = 0;
        int centerNumber = 0;

        for (int i = 0; i < 5; i++) {
            int number = Integer.parseInt(br.readLine());
            arr[number]++;
            sum += number;
        }

        int count = 0;
        for (int i = 0; i < 101; i++) {
            while (arr[i] > 0) {
                count++;
                arr[i]--;

                if (count == 3) {
                    centerNumber = i;
                    break;
                }
            }
        }

        sb.append(sum / 5).append("\n").append(centerNumber);
        System.out.println(sb);
        br.close();
    }
}