배열이 여러개 주어질 때 서로 다른 배열끼리 가장 큰 원소의 차이를 출력하는 문제.

Solution

그리디? 라고도 볼 수 있다.
일단 차가 가장 크려면 각각 다른 배열의 최대와 최소를 빼줘야 한다. 중간에 있는 원소는 필요 없다.

간단하고 직관적으로 짜려면 모든 배열의 최대와 최소를 구한 뒤 같은 배열이라면 두번째 최대 혹은 두번째 최소로 답을 구할 수 있긴 하다. 힙으로 관리하거나 변수 2개를 쓸 수 있다. 간단한 힙은 O(n logn)

1pass로도 간단히 구할 수 있는데 죽 돌면서 답을 갱신할 때 같은 배열은 빼고 계산해주면 된다. O(n)

Source Code

O(n logn)

class Solution:
    def maxDistance(self, arrays: List[List[int]]) -> int:
        mins = []
        maxes = []

        for i in range(len(arrays)):
            heapq.heappush(mins, [arrays[i][0], i])
            heapq.heappush(maxes, [-arrays[i][-1], i])

        minimum = heapq.heappop(mins)
        maximum = heapq.heappop(maxes)
        if minimum[1] == maximum[1]:
            minimum2 = heapq.heappop(mins)
            maximum2 = heapq.heappop(maxes)
            return max(abs(minimum2[0] + maximum[0]), abs(minimum[0] + maximum2[0]))

        return abs(minimum[0] + maximum[0])

O(n)

class Solution:
    def maxDistance(self, arrays: List[List[int]]) -> int:
        minimum, maximum = arrays[0][0], arrays[0][-1]
        ans = 0

        for a in arrays[1:]:
            ans = max(ans, abs(maximum - a[0]), abs(a[-1] - minimum))
            maximum = max(maximum, a[-1])
            minimum = min(minimum, a[0])

        return ans

624. Maximum Distance in Arrays

Problem link

Problem Summary

Solution

Source Code

O(n logn)

O(n)