크기가 n + 1인 리스트 nums가 있고, 그 요소들은 1, 2, ..., n 범위에서 선택되었다고 가정해 보겠습니다. 비둘기집 원리(서랍 원리)에 따르면 요소의 개수가 선택 가능한 값의 종류보다 많기 때문에 반드시 중복된 값이 하나 이상 존재합니다. 이때 우리는 그 중복 값을 찾아야 하며, 목표는 O(n) 시간 복잡도와 상수 공간으로 문제를 해결하는 것입니다.
예를 들어 입력이 nums = [2, 1, 4, 3, 5, 4]라면 출력은 4가 됩니다.
해결 접근 방법
핵심 아이디어는 간단한 산술 연산입니다. 1부터 n까지의 합은 공식으로 바로 계산할 수 있으므로, 실제 리스트의 합에서 기대 합을 빼면 그 차이가 곧 중복 값이 됩니다.
q := nums에 있는 모든 요소의 합
n := nums의 크기
v := ((n - 1) * n / 2)의 내림값, 즉 1부터 (n - 1)까지의 합
return q - v
동작 원리
리스트의 길이가 n이라면 요소들은 1부터 n - 1 사이의 값으로 이루어져 있습니다. 중복이 없다면 전체 합은 1부터 n - 1까지의 합, 즉 (n - 1) × n ÷ 2와 같습니다. 따라서 실제 합(q)에서 이 기대 합(v)을 빼면 남는 값이 바로 한 번 더 등장한 중복 숫자입니다.
예제 코드
다음 구현을 통해 더 잘 이해해 보겠습니다.
def solve(nums): q = sum(nums) n = len(nums) v = (n - 1) * (n) // 2 return q - v nums = [2,1,4,3,5,4] print(solve(nums))
입력
[2,1,4,3,5,4]
출력
4
이 방법은 리스트를 한 번만 순회하며 합을 구하므로 시간 복잡도가 O(n)이고, 추가 변수 몇 개만 사용하므로 공간 복잡도는 O(1)입니다. 정렬이나 해시맵 없이도 중복 요소를 효율적으로 찾을 수 있는 실용적인 기법입니다.