리스트 nums가 주어졌을 때, 리스트 안의 모든 숫자가 각각 짝수 번 나타나는지 확인해야 하는 문제입니다. 이때 추가적인 메모리 사용 없이, 즉 상수 공간(constant space)만으로 해결하는 것이 핵심 조건입니다.
예를 들어 입력이 nums = [8, 9, 9, 8, 5, 5]라면 출력은 True가 됩니다. 모든 숫자가 두 번씩 등장하기 때문입니다.
해결 접근 방식
다음 단계에 따라 문제를 해결할 수 있습니다.
nums의 길이가 홀수라면 즉시 False를 반환합니다. 요소 개수가 홀수이면 모든 값이 짝수 번 등장하는 것은 불가능합니다.- 리스트
nums를 정렬합니다. 정렬하면 같은 값들이 서로 인접하게 배치됩니다. - 인덱스 i를 1부터 리스트 길이까지 반복하면서,
nums[i]와nums[i-1]이 같으면 두 값을 모두 0으로 만듭니다. 이렇게 하면 짝수 번 등장한 쌍이 하나씩 제거됩니다. - 마지막으로
nums의 모든 요소의 합이 0이면 True, 그렇지 않으면 False를 반환합니다. 홀수 번 남은 요소가 있다면 합이 0이 되지 않기 때문입니다.
예제 코드
아래 구현을 통해 동작 방식을 더 쉽게 이해할 수 있습니다.
def solve(nums):
# 길이가 홀수면 짝수 번 등장 불가능
if len(nums) & 1:
return False
nums.sort()
# 인접한 같은 값의 쌍을 0으로 제거
for i in range(1, len(nums)):
if nums[i] == nums[i - 1]:
nums[i] = nums[i - 1] = 0
# 모든 요소가 제거되었는지 확인
return sum(nums) == 0
nums = [8, 9, 9, 8, 5, 5]
print(solve(nums))입력
[8, 9, 9, 8, 5, 5]
출력
True
참고: 이 방식의 한계와 대안
위 알고리즘은 모든 요소가 양수일 때 안전하게 동작합니다. 음수가 포함되면 서로 다른 값의 합이 우연히 0이 되어 잘못된 결과를 낼 수 있습니다. 예를 들어 [-1, 1]은 각각 한 번씩만 등장했지만 합이 0이라 True를 반환하게 됩니다.
음수까지 일반적으로 처리해야 한다면 collections.Counter를 사용하는 방법이 더 안전하고 직관적입니다.
from collections import Counter
def solve(nums):
return all(count % 2 == 0 for count in Counter(nums).values())Counter 기반 방법은 O(n)의 추가 메모리를 사용하지만, 어떤 값이 몇 번 등장했는지 명확하게 검사하므로 실무에서는 더 권장되는 접근입니다. 반면 메모리 제약이 엄격하고 요소가 양수임이 보장된다면 앞서 소개한 정렬 기반 방법이 유용합니다.