Missing Number

Q: Missing Number의 시간 복잡도는 얼마인가요?

합과 XOR를 사용하는 두 해결 방법 모두 O(n) 시간과 O(1) 의 추가 공간으로 실행됩니다. 각 값을 한 번씩 읽고 숫자 하나만 저장하기 때문입니다. 후보를 찾을 때마다 목록을 검색하면 O(n²) 이 걸립니다. 먼저 정렬한 다음 빠진 값을 찾으면 O(n log n) 이 걸립니다.

Q: 합 공식과 XOR 중 무엇을 사용해야 할까요?

둘 다 한 번 순회하며 상수 메모리를 사용합니다. 합계가 설명하기는 더 쉽지만, 32비트 산술에서는 n(n+1) 의 곱이 n 이 약 46,000을 넘으면 오버플로가 발생하므로 64비트 산술이 필요합니다. XOR는 오버플로가 발생하지 않습니다. Python, Ruby 및 무제한 정수를 지원하는 다른 언어에서는 차이가 사라집니다.

쉬움비트 조작 수학과 시뮬레이션

+10

0부터 n 사이의 서로 다른 정수 n개로 이루어진 목록 nums가 주어집니다. 0부터 n까지의 범위에는 숫자가 n+1개 있으므로, 그중 정확히 하나가 목록에 없습니다. 누락된 숫자를 반환하세요.

함수

missingNumber(nums: integer-array) → integer

numsinteger-array: 0부터 n까지의 범위에 있는 서로 다른 정수 n개를 순서에 상관없이
반환값integer: nums에 없는 0부터 n까지의 숫자 하나

제약 조건

n == nums.length
1 ≤ n ≤ 10⁴
0 ≤ nums[i] ≤ n
nums의 모든 값은 서로 다릅니다.

예제

입력: nums = [4, 2, 0, 1]
출력: 3
설명: 목록에는 값이 4개 있으므로 범위는 0부터 4까지입니다. 목록에는 0, 1, 2, 4가 있고, 3은 일치하는 항목이 없는 유일한 숫자입니다.

후속 질문

목록이 정렬되어 있다면 이진 검색으로 O(log n) 시간 안에 누락된 숫자를 찾을 수 있을까요?

힌트

하나씩 열어 보세요. 열 때마다 조금 더 알려 줍니다.

3개 중 0개 열림

풀이

목록에 무엇이 들어 있어야 하는지 정확히 알고 있습니다. 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을 사용하세요.

자주 묻는 질문3

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 및 무제한 정수를 지원하는 다른 언어에서는 차이가 사라집니다.

def missingNumber(nums):
    # 여기에 코드를 작성하세요

테스트 #1

테스트 #2

테스트 #3

인자

nums = [4, 2, 0, 1]

예상 출력

Missing Number

함수

제약 조건

예제

힌트

풀이

모든 후보를 확인하세요

예상 합계에서 합계를 뺍니다

인덱스를 값과 XOR하세요

함정과 경계 사례

자주 묻는 질문3

비슷한 문제