Leetcode 624 Maximum Distance in Arrays (C++)

https://leetcode.com/problems/maximum-distance-in-arrays/

 

class Solution {
public:
    int maxDistance(vector<vector<int>>& arrays) {
        

        int ans=0;
        int M=arrays[0].back();
        int m=arrays[0].front();
    

        for(int i=1;i<arrays.size();i++){
            
            ans=max(ans, max(abs(arrays[i].back()-m), abs(M-arrays[i].front())));
            m=min(m, arrays[i].front());
            M=max(M, arrays[i].back());

            
        }


        return ans;
    }
};

1. 문제

임의 개수의 정수 배열이 오름차순 정렬된 상태로 주어진다. 두 정수 a, b 사이의 거리를 abs(a, b)로 정의할 때, 서로 다른 배열의 두 정수의 최대 거리를 구하라.

2. 풀이

거리가 최대가 되려면 한 배열의 최댓값에서 다른 배열의 최솟값을 빼야 한다. 이를 이용하여 풀어보자.

        int ans=0;
        int M=arrays[0].back();
        int m=arrays[0].front();

우선 변수를 초기화해준다. M은 탐색 이전 배열까지의 최댓값, m은 탐색 이전 배열까지의 최솟값을 뜻한다.

        for(int i=1;i<arrays.size();i++){
            
            ans=max(ans, max(abs(arrays[i].back()-m), abs(M-arrays[i].front())));
            m=min(m, arrays[i].front());
            M=max(M, arrays[i].back());

            
        }

이후 각 배열에 대해 거리의 최댓값을 갱신해준다. 현재 배열에 대해 거리의 최댓값은 다음의 방법으로 구할 수 있다.

• 이전 배열까지의 최댓값-현재 배열의 최솟값
• 현재 배열의 최댓값-이전 배열까지의 최솟값

거리는 서로 다른 두 배열에서 구해야 하므로 거리를 먼저 갱신한 후 최댓값과 최솟값을 갱신해준다. 

연산이 끝나고 ans를 리턴하면 정답을 구할 수 있다.