📙[Algo] 23.12.29 알고리즘

14400번: 편의점 2

문제 요약
모든 고객들과의 거리의 합이 최소가 되는 지점에 편의점 설치 거리 = Math.abs(x1-x2) + Math.abs(y1-y2) 그 최소 거리의 합을 출력해라

시간 제한
2초(2억개 연산)

입력
주요 고객들의 수 n (1≤n≤100,000) n 줄에 고객들의 위치 (x,y) (-1,000,000≤x,y≤1,000,000)

출력
최소 거리 합 출력 

 

접근법

• 안테나 문제와 비슷하게 접근하는 문제
• 만약 하나 하나 세워보며, 거리 비교를 했을 때,
  • 최악의 상황에서 100,000명의 고객들의 좌표가 (-1,000,000 , -1,000,000) … (1,000,000 , 1,000,000) 예시로 주어질 경우 2,000,000*100,000, 즉, 2천억개의 연산이 필요하다.
  • 모든 좌표 일일이 거리 비교하는 것은 비효율적이라고 판단!
• 예시로 생각해보았을 때
  • 거리의 합이 30이 되는 좌표가 어디쯤일까?
    • (2, 4)
      • 1+3+1+4+2+2+5+12
      ⇒ 우리가 이 식을 계산하는 과정에서 x좌표와 y좌표가 따로 계산되는 것을 알 수 있었다.
    • ⇒ 결국, 안테나 문제처럼 중간값이 가장 최소 거리가되는 것을 알 수 있음
• 주의할 점!!!
  • 거리를 저장할 변수의 타입은 int가 아니라 long이어야 한다.

코드

package com.company;


import java.io.*;
import java.util.Arrays;
import java.util.StringTokenizer;

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()); // 주요 고객들의 수

        // 고객들의 좌표를 담을 배열
        int[] locationX = new int[N];
        int[] locationY = new int[N];

        // 고객들의 좌표 입력 받기
        StringTokenizer st;
        for(int i=0; i<N; i++){
            st = new StringTokenizer(br.readLine());
            locationX[i] = Integer.parseInt(st.nextToken()); // x좌표
            locationY[i] = Integer.parseInt(st.nextToken()); // y좌표
        }

        // 오름차순 정렬
        Arrays.sort(locationX);
        Arrays.sort(locationY);

        // 중앙값 인덱스 찾기
        int idx = N%2==0? N/2-1: N/2;

        // 가장 최소거리가 될 좌표(편의점 세울 위치)
        int centerX = locationX[idx];
        int centerY = locationY[idx];

        // 최소 거리 구하기
        long answer = 0;
        for(int i=0; i<N; i++){
            answer += Math.abs(locationX[i]-centerX) + Math.abs(locationY[i]-centerY);
        }

        System.out.println(answer);

    }
}