두 개의 숫자 리스트 L1과 L2가 있다고 가정해 보겠습니다. 각 리스트의 길이는 n이며, 모든 값은 자신이 속한 리스트 안에서 유일하고, 값의 범위는 1부터 n까지입니다. 이때 L1을 L2로 변환하는 데 필요한 인접 요소 교환(swap)의 최소 횟수를 구해야 합니다.
예를 들어 입력이 L1 = [0, 1, 2, 3], L2 = [2, 0, 1, 3]이라면 출력은 2가 됩니다. 먼저 1과 2를 교환하면 L1은 [0, 2, 1, 3]이 되고, 이어서 0과 2를 교환하면 [2, 0, 1, 3]이 되어 L2와 같아지기 때문입니다.
문제 해결 접근 방식
이 문제는 역순 쌍(inversion)의 개수를 세는 방식으로 해결할 수 있습니다. L2에 나타나는 순서대로 L1에서 해당 값을 찾아 제거하면서, 그 값 앞에 있던(즉, 건너뛰어야 하는) 요소의 수를 누적하면 됩니다. 구체적인 단계는 다음과 같습니다.
- 결괏값 ans를 0으로 초기화합니다.
- L2의 각 요소 req에 대해 다음을 반복합니다.
- L1에서 req의 위치 i를 찾습니다.
- L1에서 i번째 요소를 삭제합니다.
- ans에 i를 더합니다.
- 모든 반복이 끝나면 ans를 반환합니다.
여기서 핵심 아이디어는, L2의 순서대로 요소를 하나씩 확정할 때 그 요소가 L1에서 차지하고 있던 위치만큼 인접 스왑이 필요하다는 점입니다. 요소를 제거하면 뒤쪽 요소들이 앞으로 당겨지므로, 남은 요소들의 상대적 순서는 그대로 유지됩니다.
구현 예제
다음 코드를 통해 더 잘 이해할 수 있습니다.
class Solution:
def solve(self, L1, L2):
ans = 0
for req in L2:
i = L1.index(req)
L1.pop(i)
ans += i
return ans
ob = Solution()
L1 = [0, 1, 2, 3]
L2 = [2, 0, 1, 3]
print(ob.solve(L1, L2))입력
[0, 1, 2, 3], [2, 0, 1, 3]
출력
2
시간 복잡도 분석
리스트의 index() 연산과 pop() 연산은 각각 O(n)의 시간이 걸리므로, 위 알고리즘의 전체 시간 복잡도는 O(n²)입니다. 리스트 길이가 매우 큰 경우에는 펜윅 트리(Fenwick Tree)나 세그먼트 트리를 활용해 O(n log n)으로 최적화할 수 있습니다. 하지만 일반적인 코딩 테스트 수준의 입력 크기에서는 위 구현으로 충분히 빠르게 동작합니다.