Missing Number
0부터 n 사이의 서로 다른 정수 n개로 이루어진 목록 nums가 주어집니다. 0부터 n까지의 범위에는 숫자가 n+1개 있으므로, 그중 정확히 하나가 목록에 없습니다. 누락된 숫자를 반환하세요.
함수
- numsinteger-array
- 0부터 n까지의 범위에 있는 서로 다른 정수 n개를 순서에 상관없이
- 반환값integer
- nums에 없는 0부터 n까지의 숫자 하나
제약 조건
n == nums.length1 ≤ n ≤ 1040 ≤ nums[i] ≤ n-
nums의 모든 값은 서로 다릅니다.
예제
- 입력
- nums = [4, 2, 0, 1]
- 출력
- 3
- 설명
- 목록에는 값이 4개 있으므로 범위는 0부터 4까지입니다. 목록에는 0, 1, 2, 4가 있고, 3은 일치하는 항목이 없는 유일한 숫자입니다.
- 입력
- nums = [1]
- 출력
- 0
- 설명
- 값이 하나일 때 범위는 0과 1입니다. 목록에는 1이 있으므로 0은 없습니다.
- 입력
- nums = [0, 1, 2]
- 출력
- 3
- 설명
- 3보다 작은 모든 숫자가 있으므로, 빠진 숫자는 범위의 끝값인 3입니다. 이는 목록의 인덱스가 아니므로 끝값을 주의해야 합니다.
제출 시 숨은 테스트 +13개
후속 질문
목록이 정렬되어 있다면 이진 검색으로 O(log n) 시간 안에 누락된 숫자를 찾을 수 있을까요?
힌트
하나씩 열어 보세요. 열 때마다 조금 더 알려 줍니다.
목록에 어떤 숫자가 들어가야 하는지 정확히 알고 있습니다.
0부터n까지의 모든 정수입니다. 이 전체 범위에 대해 계산한 숫자 하나를 목록에 대해 계산한 같은 숫자와 비교할 수 있을까요?0부터n까지의 정수를 모두 더하면n(n+1)/2가 되고, 목록의 합은 누락된 값만큼 정확히 더 작습니다. XOR는 오버플로 위험 없이 같은 방식으로 작동합니다. 값과 자기 자신을 XOR하면0이 되기 때문입니다.누적 XOR을 사용해 리스트를 한 번 순회합니다.
n에서 시작하고, 각 인덱스i에서i와nums[i]를 모두 XOR합니다. 두 번 나타나는 모든 숫자는 서로 상쇄되고, 누락된 숫자만 남습니다.
풀이
목록에 무엇이 들어 있어야 하는지 정확히 알고 있습니다. 0부터 n까지의 모든 정수입니다. 각 숫자를 하나씩 검색하는 방법도 작동하지만, 숫자마다 전체 목록을 다시 훑어야 합니다. 대신 전체 범위와 목록을 각각 하나의 요약값, 즉 합계나 XOR 값으로 압축하면, 두 값의 차이가 누락된 숫자입니다. 이렇게 하면 한 번만 순회하고 추가 메모리도 필요하지 않습니다.
모든 후보를 확인하세요
정답이지만 가장 큰 테스트에서는 끝나지 않음
핵심 아이디어
정답은 0부터 n까지의 n+1개 숫자 중 하나입니다. 순서대로 하나씩 가져와 목록에서 찾습니다. 어떤 값과도 일치하지 않는 첫 번째 후보가 누락된 숫자입니다.
범위의 모든 숫자는 목록에 있거나 정답이며, 목록에 중복 항목이 없으므로 검색에 실패하는 후보는 정확히 하나뿐입니다. 따라서 이 방법은 정확합니다.
각 후보마다 최대 n개의 값을 검색해야 하므로 느립니다. 누락된 숫자가 범위의 끝부분에 있으면 거의 모든 후보를 검색하게 됩니다. n = 10^4이고 누락된 숫자가 끝부분에 있는 경우 비교 횟수는 약 5 × 10^7회입니다. 목록의 길이를 두 배로 늘리면 작업량은 네 배가 됩니다.
알고리즘
candidate를0부터n까지 포함하여 반복합니다.nums에서candidate와 같은 값을 검색합니다.- 검색 결과 해당 값을 찾으면 다음 후보로 넘어갑니다.
- 일치하는 값 없이 검색이 끝나면
candidate를 반환합니다.
def missingNumber(nums):
n = len(nums)
for candidate in range(n + 1):
# "in" on a list scans it from the start: O(n) per candidate.
if candidate not in nums:
return candidate
return -1예상 합계에서 합계를 뺍니다
핵심 아이디어
빠진 것이 없다면 목록에는 0부터 n까지의 모든 숫자가 들어 있고, 이 숫자들의 합은 n(n+1)/2입니다. 실제 목록은 이 전체 집합에서 숫자 하나를 뺀 것이므로, 합은 정확히 그 숫자만큼 부족합니다.
[4, 2, 0, 1]의 경우 n은 4이고 전체 범위의 합은 4 × 5 / 2 = 10입니다. 목록의 합은 7이므로, 10에서 7을 빼면 3이 남습니다.
목록을 한 번 순회하며 합을 구하므로 시간 복잡도는 O(n)이고, 누적 합계 하나만 유지하면 됩니다. 여기서 전체 합은 최대 약 5 × 10^7이므로 32비트 정수에 들어갑니다. 훨씬 큰 n에서는 공식의 계산 결과가 32비트 int의 범위를 넘으므로, Java, C, C++, C# 및 Rust 버전은 64비트로 계산합니다.
알고리즘
n을nums의 길이라고 합시다.- 전체 합
n(n+1)/2을 계산합니다. nums의 모든 값을 더합니다.- 전체 합에서 리스트의 합을 뺀 값을 반환합니다.
def missingNumber(nums):
n = len(nums)
expected = n * (n + 1) // 2
return expected - sum(nums)인덱스를 값과 XOR하세요
핵심 아이디어
XOR은 쌍을 상쇄합니다. a ^ a는 0이고, a ^ 0은 a이며, 연산 순서는 중요하지 않습니다. 따라서 하나의 값만 빼고 모든 값이 두 번씩 나타나는 숫자 묶음에 XOR을 적용하면 쌍은 사라지고 그 값만 남습니다.
문제에서 이러한 묶음을 만드세요. 인덱스 0부터 n까지와 nums의 값들을 함께 묶습니다. 목록에 있는 숫자는 인덱스와 값으로 한 번씩 나타나므로 상쇄됩니다. 누락된 숫자는 인덱스로만 나타나므로 남습니다. 반복문은 인덱스 0부터 n-1까지 방문하므로, 마지막 인덱스까지 포함하려면 결과를 n으로 시작하세요.
[4, 2, 0, 1]의 경우: 4에서 시작한 다음 0과 4, 1과 2, 2와 0, 3과 1을 차례로 XOR합니다. 4, 2, 1, 0은 모두 상쇄되고 3이 남습니다. 이 방법은 실행 중인 값 하나만 사용하는 한 번의 순회이며, 합계와 달리 n에서 이미 사용하는 비트 범위를 넘어 커지지 않으므로 오버플로가 발생할 수 없습니다.
알고리즘
result를nums의 길이인n으로 설정합니다.- 각 인덱스
i에 대해result를i및nums[i]와 XOR 연산합니다. result를 반환합니다.
def missingNumber(nums):
# Start with n, the one index the loop below never reaches.
result = len(nums)
for i, value in enumerate(nums):
result ^= i ^ value
return result
함정과 경계 사례
대부분의 오답은 범위의 양 끝에서 발생합니다.
n자체가 빠질 수 있다는 점을 잊는 경우입니다.[0, 1, 2]에서 정답은 3이며, 이는 목록의 인덱스가 아닙니다. XOR 방식은n에서 시작해야 하며,nums[i] != i인 첫 번째 위치를 찾는 정렬된 배열의 순회 방식에서는 모든 위치가 일치할 때n을 반환해야 합니다.- 잘못된 범위 크기를 사용하는 경우입니다. 숫자는
0부터n까지이므로n+1개이며, 전체 합은(n-1)n/2가 아니라n(n+1)/2입니다. 0이 항상 있다고 가정하는 경우입니다.[1]에서 정답은 0이며, 검색을 1에서 시작하는 코드는 이를 놓칩니다.- 합을 사용하는 방식에서 오버플로가 발생하는 경우입니다. 32비트 산술에서는 2로 나누기 전에 곱
n(n+1)이n이 약 46,000을 넘으면 오버플로되며,n(n+1)/2자체도 약 65,000부터는 표현할 수 없습니다. 64비트 산술이나 XOR을 사용하세요.
자주 묻는 질문4
Missing Number의 시간 복잡도는 얼마인가요?
합과 XOR를 사용하는 두 해결 방법 모두 O(n) 시간과 O(1)의 추가 공간으로 실행됩니다. 각 값을 한 번씩 읽고 숫자 하나만 저장하기 때문입니다. 후보를 찾을 때마다 목록을 검색하면 O(n²)이 걸립니다. 먼저 정렬한 다음 빠진 값을 찾으면 O(n log n)이 걸립니다.
XOR는 왜 누락된 숫자를 찾을까요?
숫자를 자기 자신과 XOR하면 0이 되고, 0과 XOR하면 아무것도 바뀌지 않으며, 순서는 상관없습니다. 0부터 n까지의 모든 인덱스를 모든 값과 함께 XOR하면 목록에 있는 각 숫자는 두 번씩 나타나 서로 상쇄됩니다. 누락된 숫자는 인덱스로 한 번만 나타나므로, 그 값이 결과가 됩니다.
합 공식과 XOR 중 무엇을 사용해야 할까요?
둘 다 한 번 순회하며 상수 메모리를 사용합니다. 합계가 설명하기는 더 쉽지만, 32비트 산술에서는 n(n+1)의 곱이 n이 약 46,000을 넘으면 오버플로가 발생하므로 64비트 산술이 필요합니다. XOR는 오버플로가 발생하지 않습니다. Python, Ruby 및 무제한 정수를 지원하는 다른 언어에서는 차이가 사라집니다.
해시 집합으로 Missing Number를 풀 수 있나요?
네. 모든 값을 집합에 넣은 다음, 0부터 n까지 확인하고 집합에 없는 첫 번째 숫자를 반환하세요. 이 방법은 O(n) 시간이 걸리지만 O(n)의 추가 메모리를 사용하며, 합계 및 XOR 방법은 추가 메모리를 사용하지 않습니다.
비슷한 문제
같은 아이디어를 쓰는 문제입니다. 두세 개를 풀면 패턴이 몸에 익습니다.
Python
def missingNumber(nums):
# 여기에 코드를 작성하세요케이스 1
케이스 2
케이스 3
입력
nums = [4, 2, 0, 1]
기대값
3