Python에서 요소 순서를 유지한 채 두 리스트를 병합하는 방법의 수 구하기

두 개의 리스트 nums1과 nums2가 있다고 가정해 보겠습니다. 이때 병합 과정에서 각 리스트 내부 요소들의 상대적인 순서는 그대로 유지되어야 한다는 제약 조건이 있습니다.

예를 들어 [1,2,3]과 [4,5,6]을 병합한다면, [1,4,2,3,5,6]이나 [1,2,3,4,5,6]처럼 유효한 병합 결과가 여러 가지 존재할 수 있습니다. 두 리스트의 크기가 각각 N과 M일 때, 유효한 병합 결과를 만들 수 있는 총 경우의 수를 구해야 합니다. 만약 답이 너무 커진다면 10^9 + 7로 나눈 나머지를 반환하면 됩니다.

예를 들어 입력이 N = 5, M = 3이라면 출력은 56이 됩니다.

문제 해결 접근 방법

이 문제는 조합론을 이용하면 간단하게 해결할 수 있습니다. 핵심 아이디어는 다음과 같습니다.

병합된 최종 리스트의 길이는 N + M입니다. 전체 N + M개의 자리 중에서 첫 번째 리스트의 요소들이 들어갈 N개의 위치를 선택하면, 남은 자리에는 두 번째 리스트의 요소들이 자동으로 순서대로 배치됩니다. 각 리스트 내부의 순서는 어차피 고정되어 있으므로, 위치만 정해지면 병합 결과가 하나로 결정됩니다.

따라서 정답은 이항계수 C(N+M, M), 즉 N+M개 중에서 M개(또는 N개)의 위치를 뽑는 조합의 수와 같습니다.

알고리즘 단계

ret := 1 로 초기화합니다.
i를 N+1부터 N+M까지 반복하면서 ret에 i를 곱합니다. (N+M)! / N! 을 계산하는 과정입니다.
i를 1부터 M까지 반복하면서 ret을 i로 나눕니다. (정수 나눗셈 사용) 이렇게 하면 M! 로 나누어져 C(N+M, M)이 됩니다.
마지막으로 ret mod (10^9 + 7)을 반환합니다.

구현 예제

아래 구현을 통해 더 잘 이해해 보겠습니다.

def solve(N, M):
   ret = 1
   # (N+1)부터 (N+M)까지 곱하기 → (N+M)! / N!
   for i in range(N + 1, N + M + 1):
      ret *= i
   # 1부터 M까지 나누기 → M! 제거하여 조합 계산
   for i in range(1, M + 1):
      ret //= i
   return ret % (10**9 + 7)

N = 5
M = 3
print(solve(N, M))

입력

N = 5, M = 3

출력

복잡도 분석

시간 복잡도는 두 반복문에 의해 O(M)이며, 공간 복잡도는 추가 변수만 사용하므로 O(1)입니다. N과 M이 커져도 모듈러 연산 덕분에 오버플로우 없이 안전하게 결과를 얻을 수 있습니다.