LeetCode [1460]: Make Two Arrays Equal by Reversing Subarrays

📌 LeetCode [1460]: Make Two Arrays Equal by Reversing Subarrays

🔗 문제 링크

---

문제 설명 📄

두 개의 배열 target과 arr가 주어집니다.
다음과 같은 연산을 무한히 수행할 수 있습니다:

• arr에서 서브배열을 선택하고, 그 순서를 뒤집습니다.

위 조건으로 배열 arr을 target과 동일하게 만들 수 있는지 판단하여 True 또는 False를 반환하세요.

---

문제 접근 방식 📋

1. 문제의 본질:
   • 서브배열의 순서를 뒤집는 연산은 배열 요소의 순서를 변경할 수 있지만, 요소 자체를 추가하거나 제거할 수는 없습니다.
   • 따라서 두 배열이 동일해지려면 두 배열의 요소와 각 요소의 빈도수가 같아야 합니다.
2. 카운터를 활용한 비교:
   • Python의 collections.Counter를 활용하여 두 배열의 요소 빈도를 계산합니다.
   • 두 Counter 객체가 동일하면 True를 반환, 그렇지 않으면 False를 반환합니다.

---

Solution 💻

from collections import Counter

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

시간 복잡도 분석 ⏲️

• Counter 생성: (O(n)), (n)은 배열의 길이.
• Counter 비교: (O(k)), (k)는 고유 숫자의 개수.
• 최종 시간 복잡도: (O(n + k)).

공간 복잡도 분석 🗄️

• Counter 저장 공간: (O(k)), 고유 숫자의 개수.

---