코드트리 [자바 java] 마라톤 중간에 택시타기

https://www.codetree.ai/missions/8/problems/taking-a-taxi-in-the-middle-of-the-marathon?utm_source=clipboard&utm_medium=text 

코드트리 | 코딩테스트 준비를 위한 알고리즘 정석

 

이차원배열 내의 점들이 주어지고 이 점들을 순차적으로 방문해야한다고 가정했을 때 가능한 최소의 값이 나오도록 하나의 점을 빼는 경우를 구하는 문제이다.

여기서의 값은 현재 인덱스와 바로 앞, 뒤의 인덱스의 차이를 모두 더한 것을 의미한다.

 

이 문제는 lr테크닉을 사용한다.

LR Technique

이렇게 배열이 주어지고, 배열n 을 제외하고 위와 같이 앞,뒤의 차이를 모두 더한 값을 출력하라는 문제가 있다고 가정하자.

이 문제를 브루트포스로 풀면 시간복잡도가 O(n)이다. 하지만 LRTechnique를 이용하면 O(1)로 풀 수 있다 

위와 같이 L과 R의 배열을 만들고, L은 해당 인덱스보다 앞의 인덱스와의 차이 + L[인덱스-1]의 값을 의미하고, R은 해당 인덱스보다 뒤의 인덱스와의 차이 + R[인덱스 +1]의 값을 의미한다.

 

 

이렇게 n의 인덱스보다 앞의 값은 L을 이용해서 바로 구할 수 있고, 뒤의 값은 R을 이용해서 구할 수 있다. 여기에다가 n의 바로 앞, 뒤의 인덱스의 차이를 더하면 답이 바로 나온다. 이 원리는 앞서 설명했던 부분합과 유사하다.

 

이 문제는 x축과 y축을 모두 고려해야하므로 각각lr을 하나씩, 총 4개의 배열을 만들어서 rl테크닉을 사용하면 된다.

xl,xr,yl,yr 을 다 채운 후, 점 하나를 뺀 값 중 최솟값을 구해야하므로 1번과 n번을 제외한 모든 점을 한번씩 빼서 나온 값중 가장 작은 값을 출력한다.

 

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


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());

        StringTokenizer st;
        int[] x = new int[n];
        int[] y = new int[n];

        for(int i = 0;i<n;i++){
            st = new StringTokenizer(br.readLine());

            x[i] = Integer.parseInt(st.nextToken());
            y[i] = Integer.parseInt(st.nextToken());

        }

        int[] xl = new int[n]; //x축의 l
        int[] xr = new int[n]; //x축의 r
        int[] yl = new int[n]; //y축의 l
        int[] yr = new int[n]; //y축의 r

        
//l들 채우기
        for(int i = 1;i<n;i++){
            xl[i] = Math.abs(x[i] - x[i-1]) + xl[i-1];
            yl[i] = Math.abs(y[i] - y[i-1]) + yl[i-1];
        }
//x들 채우기
        for(int i = n-2;i>=0;i--){
            xr[i] = Math.abs(x[i] - x[i+1]) + xr[i+1];
            yr[i] = Math.abs(y[i] - y[i+1]) + yr[i+1];
        }

        int min = Integer.MAX_VALUE;

        for(int i = 1;i<n-1;i++){
            //차례로 뺀 상태에서의 값 구하고 min값과 비교
            int now = (xl[i-1] + xr[i+1] + Math.abs(x[i-1] - x[i+1]) 
             + yl[i-1] + yr[i+1] + Math.abs(y[i-1] - y[i+1]));

             min = Math.min(min,now);

        }

        System.out.println(min);


    }
}