두 개의 숫자 리스트 A와 B가 주어졌다고 가정해 보겠습니다. 우리는 리스트 A에서 연속된 부분 리스트(sublist)를 골라 뒤집을 수 있으며, 이 작업은 원하는 만큼 몇 번이든 반복할 수 있습니다. 목표는 이러한 뒤집기 작업만으로 A를 B로 변환할 수 있는지 판단하는 것입니다.
예를 들어, 입력이 A = [2, 3, 4, 9, 10], B = [4, 3, 2, 10, 9]라면 결과는 True가 됩니다. [2, 3, 4] 구간과 [9, 10] 구간을 각각 한 번씩 뒤집으면 B와 동일한 리스트를 얻을 수 있기 때문입니다.
핵심 아이디어
길이가 2인 부분 리스트를 뒤집으면 인접한 두 원소의 위치를 맞바꾸는 효과가 있습니다. 즉, 부분 리스트 뒤집기를 적절히 조합하면 어떤 순열이든 만들어낼 수 있습니다. 따라서 이 문제는 결국 "두 리스트가 동일한 원소들을 동일한 빈도로 포함하고 있는가?"를 묻는 문제와 같습니다.
이를 확인하려면 각 원소의 등장 횟수를 세어 비교하면 됩니다. 첫 번째 리스트에서는 개수를 더하고, 두 번째 리스트에서는 개수를 뺀 뒤, 모든 카운트가 0이면 두 리스트는 같은 다중집합(multiset)이라는 뜻이므로 변환이 가능합니다.
해결 단계
res라는 빈 딕셔너리(맵)를 생성합니다.- nums의 각 원소 n에 대해
res[n]값을 1씩 증가시킵니다. - target의 각 원소 t에 대해
res[t]값을 1씩 감소시킵니다. - res의 모든 값이 0이면 True를 반환하고, 하나라도 0이 아니면 False를 반환합니다.
구현 코드
다음 예제 코드를 통해 더 잘 이해할 수 있습니다.
from collections import defaultdict
class Solution:
def solve(self, nums, target):
res = defaultdict(int)
for n in nums:
res[n] += 1
for t in target:
res[t] -= 1
return all(n == 0 for n in res.values())
ob = Solution()
A = [2, 3, 4, 9, 10]
B = [4, 3, 2, 10, 9]
print(ob.solve(A, B))입력
[2, 3, 4, 9, 10], [4, 3, 2, 10, 9]
출력
True
복잡도 분석
이 알고리즘은 두 리스트를 각각 한 번씩 순회하므로 시간 복잡도는 O(n)입니다. 추가로 사용되는 딕셔너리의 크기는 서로 다른 원소의 개수에 비례하므로 공간 복잡도 역시 O(n)입니다. 정렬 기반 접근(O(n log n))보다 효율적이며, collections.Counter를 활용하면 코드를 더욱 간결하게 작성할 수도 있습니다.