백준알고리즘 7571 점 모으기

백준알고리즘

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

평균 값을 구해서 결과를 도출하는게 아니라 중앙 값을 구해야 한다.

예를 들어 (1,1), (1,2), (1,6)의 평균 값을 구해서 값을 구하면 가로줄의 평균은 3이 나와서 5가나오지만

중앙값을 구해서 결과를 보면 5가 나옴을 알 수 있다.

중앙값을 구하는 공식은 Arrays.sort한 부분부터 보면 알 수 있다.

평균값 오답

import java.util.Scanner;

public class Main {
    public static void main(String args[]) throws Exception {
        Scanner scan = new Scanner(System.in);
        int N = scan.nextInt();
        int M = Integer.parseInt(scan.nextLine().trim());
        
        int xArray[] = new int[M];
        int yArray[] = new int[M];
        
        int xTotal = 0;
        int yTotal = 0;
        
        for(int i=0; i < M; i++) {
            int xPoint = scan.nextInt();
            int yPoint = Integer.parseInt(scan.nextLine().trim());
            
            xArray[i] = xPoint;
            yArray[i] = yPoint;
            
            xTotal += xPoint;
            yTotal += yPoint;
        }
        
        int xAverage = (int) Math.ceil(xTotal / M);
        int yAverage = (int) Math.ceil(yTotal / M);
        
        int transResult = 0;
        for(int i=0; i < M; i++) {
            transResult += Math.abs(xAverage - xArray[i]);
            transResult += Math.abs(yAverage - yArray[i]);
        }
        
        System.out.println(transResult);
        
        scan.close();
    }
}

중앙값 정답

import java.util.Arrays;
import java.util.Scanner;

public class Main {
    public static void main(String args[]) throws Exception {
        Scanner scan = new Scanner(System.in);
        int N = scan.nextInt();
        int M = Integer.parseInt(scan.nextLine().trim());
        
        int xArray[] = new int[M];
        int yArray[] = new int[M];
        
        int xTotal = 0;
        int yTotal = 0;
        
        for(int i=0; i < M; i++) {
            int xPoint = scan.nextInt();
            int yPoint = Integer.parseInt(scan.nextLine().trim());
            
            xArray[i] = xPoint;
            yArray[i] = yPoint;
            
            xTotal += xPoint;
            yTotal += yPoint;
        }
        
        Arrays.sort(xArray);
        Arrays.sort(yArray);
        
        int xAverage = xArray[M / 2];
        int yAverage = yArray[M / 2];
        
        int transResult = 0;
        for(int i=0; i < M; i++) {
            transResult += Math.abs(xAverage - xArray[i]);
            transResult += Math.abs(yAverage - yArray[i]);
        }
        
        System.out.println(transResult);
        scan.close();
    }
}