문제 개요
같은 길이를 가진 두 개의 숫자 리스트 A와 B가 있다고 가정해 봅시다. 우리는 임의의 인덱스 i에서 A[i]와 B[i]의 값을 서로 맞바꾸는(스왑) 연산을 원하는 만큼 수행할 수 있습니다. 목표는 두 리스트가 모두 엄격하게 증가(strictly increasing)하도록 만드는 데 필요한 최소 연산(스왑) 횟수를 구하는 것입니다.
예를 들어 입력이 A = [2, 8, 7, 10], B = [2, 4, 9, 10]라고 해 보겠습니다. A의 7과 B의 9를 한 번만 스왑하면 A = [2, 8, 9, 10], B = [2, 4, 7, 10]이 되어 두 리스트 모두 엄격하게 증가합니다. 따라서 출력은 1이 됩니다.
접근 방법: 동적 계획법(DP)
각 인덱스에서 스왑 여부에 따라 이후 상태가 달라지므로, 재귀와 동적 계획법으로 해결할 수 있습니다. 핵심은 각 위치에서 직전 위치에서 스왑했는지 여부(prev_swapped)만 기억하면 된다는 점입니다.
dp(i, prev_swapped): i번째 위치부터 끝까지 처리할 때 필요한 최소 스왑 횟수를 의미합니다.- i가 len(A)와 같으면 처리할 요소가 없으므로 0을 반환합니다.
- i가 0이면, 스왑하지 않는 경우 dp(i+1)과 스왑하는 경우 1 + dp(i+1, True) 중 작은 값을 반환합니다.
dp 함수의 세부 로직
- prev_A := A[i-1], prev_B := B[i-1]로 직전 값을 가져옵니다.
- prev_swapped가 True라면 prev_A와 prev_B를 서로 교환합니다.
- 현재 위치를 반드시 스왑해야 하는 경우(A[i] <= prev_A 또는 B[i] <= prev_B): 1 + dp(i+1, True)를 반환합니다.
- 그렇지 않다면:
- ans := dp(i+1, False) — 스왑하지 않는 경우를 먼저 고려합니다.
- A[i] > prev_B이고 B[i] > prev_A라면 스왑도 가능하므로 ans = min(ans, 1 + dp(i+1, True))로 갱신합니다.
- ans를 반환합니다.
- 메인 메서드에서는 dp(0, False)를 호출해 결과를 반환합니다.
예제 코드
class Solution:
def solve(self, A, B):
def dp(i=0, prev_swapped=False):
if len(A) == i:
return 0
elif i == 0:
return min(dp(i + 1), 1 + dp(i + 1, True))
else:
prev_A = A[i - 1]
prev_B = B[i - 1]
if prev_swapped:
prev_A, prev_B = prev_B, prev_A
if A[i] <= prev_A or B[i] <= prev_B:
return 1 + dp(i + 1, True)
else:
ans = dp(i + 1)
if A[i] > prev_B and B[i] > prev_A:
ans = min(ans, 1 + dp(i + 1, True))
return ans
return dp()
ob = Solution()
A = [2, 8, 7, 10]
B = [2, 4, 9, 10]
print(ob.solve(A, B))입력
[2, 8, 7, 10], [2, 4, 9, 10]
출력
1
정리
이 알고리즘은 각 인덱스에서 가능한 선택지가 스왑 또는 유지 두 가지뿐이라는 점을 활용한 동적 계획법 문제입니다. 각 단계에서 필요한 정보는 직전 위치의 스왑 여부뿐이므로, functools.lru_cache 같은 메모이제이션을 적용하면 시간 복잡도를 O(n)으로 최적화할 수 있습니다. 메모이제이션 없이 순수 재귀로 구현하면 호출이 중복되어 지수 시간이 걸릴 수 있으니 실전에서는 반드시 캐싱을 함께 사용하는 것이 좋습니다.