1460. Make Two Arrays Equal by Reversing Subarrays

[zeikar]

Problem link

https://leetcode.com/problems/make-two-arrays-equal-by-reversing-subarrays/

Problem Summary

적당한 subarray를 골라서 swap했을 때 target 배열을 만들 수 있는지 체크하는 문제.

Solution

두 배열의 원소의 개수를 세서 같다면 만들 수 있다.
잘 생각해보면 버블 정렬 등 swap을 통해 어떠한 순서든 생성해낼 수 있다. swap의 횟수를 묻는 문제가 아니라 단순 True/False 문제이기 때문에 이런 식으로 간단하게 구할 수 있다.

비슷하게 카운트하지 않고 정렬 후 비교하는 방법도 있는데 코드는 짧지만 O(n logn)으로 개수 세는게 O(n)으로 빠르긴 하다.

Swap 하는 최소 횟수?

그렇다면 최소 횟수로 swap 하는 방법은?
비슷한 질문들이 꽤 있어 찾아보았다

모든 subarray에 대해 swap을 해보면서 BFS 돌려보는 방식이 있다고 하는데... 시간복잡도가 높긴 한데 일단 나오긴 나올거다.
최적화가 가능할지는... 잘 모르겠네 (dp나 그리디로??)

Source Code

class Solution:
    def canBeEqual(self, target: List[int], arr: List[int]) -> bool:
        n = len(target)
        tcnt = [0] * 1001
        acnt = [0] * 1001

        for i in range(n):
            tcnt[target[i]] += 1
            acnt[arr[i]] += 1
        
        for i in range(1, 1001):
            if tcnt[i] != acnt[i]:
                return False
        return True