[2024] day 217. Leetcode 1460. Make Two Arrays Equal by Reversing Subarrays

2024년부터 새롭게 다시 시작하는 코딩테스트

2024년 8월 3일 (토)
Leetcode daily problem

1460. Make Two Arrays Equal by Reversing Subarrays

https://leetcode.com/problems/make-two-arrays-equal-by-reversing-subarrays/?envType=daily-question&envId=2024-08-03

Problem

두 개의 같은 크기(길이)의 배열 target과 arr가 주어진다.
arr를 뒤집어서 target을 같게 만들 수 있는지 판단한다.
arr을 target과 동일하게 만들 수 있으면 true를 반환하고 그렇지 않으면 false를 반환한다.

Solution

sorting

한 배열을 뒤집어서 다른 배열과 같게 만들 수 있는 방법으로는 배열의 요소들이 동일한 멀티셋(multiset)을 이루는지 검사하는 것으로 해결 할 수 있다. 즉, 두 배열의 요소들이 동일한 빈도로 나타나기만 하면 두 배열을 같게 만들 수 있다.

예를 들어
target = [1,2,3,4], arr=[2,4,1,3] 인 경우
arr에서 [2,4,1]을 뒤집으면 arr = [1,4,2,3] 이되고,
여기서 [4,2] 를 뒤집어서 [1,2,4,3] 을 만들고, [4,3] 을 뒤집어서 [1,2,3,4]로 만들 수 있다.

Code

class Solution:
    def canBeEqual(self, target: List[int], arr: List[int]) -> bool:
        return sorted(target) == sorted(arr)

Complexicity

시간 복잡도

각 배열을 정렬하는데 O(nlogn)이 소요된다.
두 정렬된 리스트를 비교하는 데 배열의 크기인 O(n)이 소요되므로, 총 시간복잡도는 O(nlogn)이다.

공간 복잡도

정렬하면서 필요한 배열 공간이 필요하므로 O(n)의 공간 복잡도가 발생한다.

---

이를 최적화해서 1개의 dictionary를 사용해 시간복잡도와 공간복잡도를 O(n)으로 해결하는 방법은,

arr 배열을 탐색하면서 빈도수에 해당하는 맵을 만들고, target 배열을 돌면서 요소들이 맵에 존재 하지 않으면 false를 반환하고, 존재 한다면 해당 요소를 -1씩 가감하면서 마지막 남은 맵의 크기가 0 이면 두 배열의 요소가 같은 것으로 판단하는 방법을 사용한다.