문제 개요
두 개의 숫자 리스트 nums1과 nums2가 주어졌다고 가정해 봅시다. 각 리스트에는 중복된 요소가 포함될 수 있습니다. 원래 이 두 리스트는 동일한 숫자 집합의 서로 다른 순열(permutation)을 나타내야 하지만, 일부 숫자가 누락되어 있습니다. 우리가 해야 할 일은 두 리스트 사이에서 빠진 숫자들을 모두 찾아 출력하는 것입니다.
예를 들어 입력이 다음과 같다고 해보겠습니다.
nums1 = [4,5,8,8,6,9]
nums2 = [3,4,4,8,8,8,6,9,5,8]
이 경우 출력은 [3, 4, 8, 8]이 됩니다. 그 이유를 자세히 살펴보면 다음과 같습니다.
- 3: nums1에는 없지만 nums2에는 존재하므로 누락된 숫자입니다.
- 4: 두 리스트 모두에 있지만, nums2에는 4가 두 개이고 nums1에는 하나만 있으므로 4 하나가 누락되었습니다.
- 8: nums2에는 8이 네 개 있고 nums1에는 두 개만 있으므로 8 두 개가 누락되었습니다.
해결 접근 방법
이 문제는 각 숫자의 등장 횟수(빈도수)를 비교하는 방식으로 해결할 수 있습니다. 단계별로 정리하면 다음과 같습니다.
c1:= nums1에 있는 각 요소의 빈도수를 담은 Counter 객체c2:= nums2에 있는 각 요소의 빈도수를 담은 Counter 객체all_nums:= nums1과 nums2에 나오는 모든 고유한 숫자를 담은 집합(set)res:= 결과를 저장할 새로운 리스트all_nums의 각 숫자 n에 대해 다음을 수행합니다.- n이 c1에 없으면 → res에 n을 c2[n]번 삽입
- n이 c2에 없으면 → res에 n을 c1[n]번 삽입
- 양쪽 모두에 있는데 c1[n] ≠ c2[n]이면 → res에 n을 |c1[n] − c2[n]|번 삽입
- res를 반환합니다.
구현 예제
파이썬의 collections.Counter를 사용하면 빈도수 계산을 아주 간단하게 처리할 수 있습니다. 다음 구현을 통해 더 잘 이해할 수 있습니다.
from collections import Counter
def solve(nums1, nums2):
c1 = Counter(nums1)
c2 = Counter(nums2)
all_nums = set(nums1) | set(nums2)
res = []
for n in all_nums:
if n not in c1:
res = res + [n]*c2[n]
elif n not in c2:
res = res + [n]*c1[n]
else:
if c1[n] != c2[n]:
res = res + [n]*abs(c1[n]- c2[n])
return res
nums1 = [4,5,8,8,6,9]
nums2 = [3,4,4,8,8,8,6,9,5,8]
print(solve(nums1, nums2))
입력
[4,5,8,8,6,9], [3,4,4,8,8,8,6,9,5,8]
출력
[3, 4, 8, 8]
시간 복잡도 분석
Counter 객체를 만드는 데는 각 리스트 길이에 비례하여 O(n)과 O(m)의 시간이 걸립니다. 이후 집합의 크기(k)만큼 순회하며 딕셔너리 조회는 상수 시간에 이루어지므로, 전체 시간 복잡도는 O(n + m)입니다. 공간 복잡도 역시 빈도수 저장과 결과 리스트를 위해 O(n + m)이 필요합니다. 또한 반복문 안에서 res = res + [n]*count 형태로 리스트를 계속 새로 만들면 성능이 저하될 수 있으므로, 실무에서는 res.extend([n]*count)나 res += [n]*count를 사용하는 것이 더 효율적입니다.