문제 설명
길이가 n + 1인 숫자 리스트 nums가 있다고 가정해 보겠습니다. 이 숫자들은 모두 1, 2, ..., n 범위 안에서 선택된 값입니다. 비둘기집 원리(Pigeonhole Principle)에 따르면, n개의 서로 다른 값으로 n + 1개의 숫자를 만들려면 반드시 하나 이상의 중복이 존재할 수밖에 없습니다. 우리의 목표는 바로 그 중복된 값을 찾아 반환하는 것입니다.
예를 들어 입력이 [2, 1, 4, 3, 3]이라면, 출력은 3이 됩니다.
접근 방법: 합의 차이 활용하기
이 문제는 수학적 성질을 이용하면 아주 간단하게 해결할 수 있습니다. 1부터 n까지의 정수 합은 공식 n × (n + 1) / 2로 계산할 수 있습니다. 여기서 리스트의 길이가 n + 1이므로, n은 곧 len(nums) − 1과 같습니다.
따라서 해결 절차는 다음과 같습니다.
- l := nums의 길이
- temp := l × (l − 1) / 2 → 즉, 1부터 n까지의 기대 합계
- temp_sum := nums의 모든 요소의 실제 합계
- (temp_sum − temp)를 반환 → 기대 합계와 실제 합계의 차이가 곧 중복 값
중복된 숫자 하나만 있으므로, 실제 합계에서 기대 합계를 빼면 남는 값이 바로 중복 요소입니다. 이 방법의 시간 복잡도는 O(n), 공간 복잡도는 O(1)로 매우 효율적입니다.
구현 예제
class Solution:
def solve(self, nums):
l = len(nums)
temp = l * (l - 1) // 2 # 1부터 n까지의 기대 합계
temp_sum = sum(nums) # 실제 합계
return temp_sum - temp
ob = Solution()
print(ob.solve([2, 1, 4, 3, 3]))
입력
[2, 1, 4, 3, 3]
출력
3
동작 원리 살펴보기
입력 [2, 1, 4, 3, 3]의 경우 리스트 길이 l은 5입니다. 따라서 1부터 4까지의 기대 합계는 5 × 4 ÷ 2 = 10이고, 실제 합계는 2 + 1 + 4 + 3 + 3 = 13입니다. 두 값의 차이인 13 − 10 = 3이 바로 중복된 숫자입니다.
참고로 파이썬 3에서 나눗셈 연산자 /는 실수(float)를 반환하므로, 위 코드처럼 정수 나눗셈 연산자 //를 사용하면 결과가 항상 정수로 깔끔하게 유지됩니다.