문제 개요
두 개의 리스트 l1과 l2가 주어졌을 때, 다음 연산을 반복 적용하여 두 리스트를 동일하게 만들어야 합니다.
연산 규칙: 임의의 부분 리스트(sublist)를 선택한 후, 해당 부분 리스트 전체를 그 요소들의 합으로 대체합니다.
목표는 이 연산을 적용한 뒤 얻을 수 있는 가장 긴 결과 리스트의 크기를 반환하는 것이며, 어떤 방식으로도 두 리스트를 같게 만들 수 없다면 -1을 반환합니다.
예시로 이해하기
입력이 l1 = [1, 4, 7, 1, 2, 10], l2 = [5, 6, 1, 3, 10]이라면 출력은 4입니다. 다음 순서로 연산을 수행하면 되기 때문입니다.
- l1의 부분 리스트 [1, 4]를 합산 → [5, 7, 1, 2, 10]
- l1의 부분 리스트 [1, 2]를 합산 → [5, 7, 3, 10]
- l2의 부분 리스트 [6, 1]을 합산 → [5, 7, 3, 10]
최종적으로 두 리스트 모두 [5, 7, 3, 10]이 되며, 결과 리스트의 길이는 4입니다.
풀이 접근 방법
이 문제는 두 리스트의 뒤(오른쪽 끝)부터 비교해 나가는 탐욕적(greedy) 기법으로 효율적으로 해결할 수 있습니다. 핵심 아이디어는 다음과 같습니다.
- 두 리스트의 마지막 요소부터 차례대로 비교를 시작합니다.
- 두 값이 같다면 하나의 매칭이 성립한 것이므로 결과 카운트(res)를 1 늘리고 양쪽 포인터를 앞으로 이동합니다.
- l1의 현재 값이 더 작다면, l1에서 바로 앞의 요소를 현재 요소에 병합(합산)하여 값을 키웁니다.
- l1의 현재 값이 더 크다면, 반대로 l2에서 바로 앞의 요소를 병합합니다.
알고리즘 단계
- i := len(l1) - 1, j := len(l2) - 1, res := 0으로 초기화합니다.
- i ≥ 0이고 j ≥ 0인 동안 다음을 반복합니다.
- l1[i] == l2[j]이면: res를 1 증가시키고 i와 j를 각각 1씩 감소시킵니다.
- l1[i] < l2[j]이면: i > 0일 때 l1[i-1] += l1[i]로 병합한 뒤 i를 1 감소시킵니다.
- l1[i] > l2[j]이면: j > 0일 때 l2[j-1] += l2[j]로 병합한 뒤 j를 1 감소시킵니다.
- 반복이 끝난 후 i == -1이고 j == -1이면 res를 반환하고, 그렇지 않으면 -1을 반환합니다.
구현 예제 (Python 코드)
class Solution: def solve(self, l1, l2): i, j, res = len(l1) - 1, len(l2) - 1, 0 while i >= 0 and j >= 0: if l1[i] == l2[j]: res, i, j = res + 1, i - 1, j - 1 elif l1[i] < l2[j]: if i > 0: l1[i - 1] += l1[i] i -= 1 elif l1[i] > l2[j]: if j > 0: l2[j - 1] += l2[j] j -= 1 return res if i == -1 and j == -1 else -1 ob = Solution() l1 = [1, 4, 7, 1, 2, 10] l2 = [5, 6, 1, 3, 10] print(ob.solve(l1, l2))
입력
[1, 4, 7, 1, 2, 10], [5, 6, 1, 3, 10]
출력
4
복잡도 분석
시간 복잡도: O(n + m) — 각 리스트의 요소를 최대 한 번씩만 처리하므로 매우 효율적입니다. (n, m은 각 리스트의 길이)
공간 복잡도: O(1) — 별도의 자료 구조 없이 포인터 변수 몇 개만 사용합니다.