[LeetCode] - 268. Missing Number

LeetCode는 프로그래밍 문제를 풀며 코딩 실력을 향상할 수 있는 온라인 플랫폼입니다. 다양한 알고리즘 및 데이터 구조 문제를 제공하며, 면접 대비에 유용합니다. 해당 문제는, LeetCode Problems에서 볼 수 있는 난이도 '쉬움 (Easy)' 단계인 "Missing Number" 문제입니다.

--> https://leetcode.com/problems/missing-number/description/

 

문제 : 

Given an array nums containing n distinct numbers in the range [0, n], return the only number in the range that is missing from the array.

---

Example 1 :

Input : nums = [3,0,1]

Output : 2

Explanation : n = 3 since there are 3 numbers, so all numbers are in the range [0,3]. 2 is the missing number in the range since it does not appear in nums.

 

Example 2 :

Input : nums = [0,1]

Output : 2

Explanation : n = 2 since there are 2 numbers, so all numbers are in the range [0,2]. 2 is the missing number in the range since it does not appear in nums.

 

Example 3 :

Input : nums = [9,6,4,2,3,5,7,0,1]

Output : 8

Explanation : n = 9 since there are 9 numbers, so all numbers are in the range [0,9]. 8 is the missing number in the range since it does not appear in nums.

 

Constraints :

• n == nums.length
• 1 <= n <= 10^4
• 0 <= nums[i] <= n
• All the numbers of nums are unique.

 

Follow up : Could you implement a solution using only O(1) extra space complexity and O(n) runtime complexity?

---

이 문제를 설명하자면, 주어진 배열에 0부터 n까지의 숫자가 포함되어 있지만, 그중 하나의 숫자가 빠져있습니다. 배열에서 빠진 숫자를 찾아 반환하는 문제입니다. 이 문제를 O(n) 시간 복잡도와 O(1) 공간 복잡도로 해결해야 합니다.

 

제 코드는 Runtime 결과를 보면 알 수 있듯이 효율적인 코드가 아니지만, 일단 저는 맨 처음에 이 문제를 풀 때는 시간, 공간 복잡도를 생각하지 않고 일단 푸는 것을 우선시했습니다. 그 후에, 점점 다듬으면서 효율성을 높이면 되니까요.

 

1. 재이의 코드 : 

class Solution {
    public int missingNumber(int[] nums) {
        Arrays.sort(nums);
        int res = 0;
        
        for (int i = 0; i < nums.length; i++) {
            if (nums[i] != i) {
                return i;
            }
        }
        return nums.length;
    }
}

 

 

• 배열 정렬:
  • Arrays.sort(nums)는 주어진 배열 nums를 오름차순으로 정렬합니다.
  • 정렬된 배열에서는 각 인덱스에 해당하는 숫자가 위치해야 합니다.
• 배열 순회 및 누락된 숫자 찾기:
  • 배열을 순회하면서 현재 인덱스 i의 값이 i와 다른지 확인합니다.
  • 만약 nums[i] != i인 경우, 인덱스 i가 배열에서 누락된 숫자입니다. 따라서 i를 반환합니다.
• 모든 숫자가 있는 경우:
  • 배열의 모든 인덱스가 해당 숫자와 일치하면, 누락된 숫자는 배열의 길이 n입니다. 이는 배열이 0부터 n-1까지의 숫자를 모두 포함하고 있는 경우에 발생합니다.

이 코드는

• 시간 복잡도: O(n log n)
• 공간 복잡도: O(1)

공간 복잡도는 조건을 충족하지만 Arrays.sort() 때문에 O(n)이 아닌 O(nlogn)이 됨으로써, 제 코드는 개선되어야 합니다.

---

2. O(n)인 코드 : 

class Solution {
    public int missingNumber(int[] nums) {
        int n = nums.length;
        int expectedSum = n * (n + 1) / 2; // 0부터 n까지의 합
        int actualSum = 0;

        for (int num : nums) {
            actualSum += num;
        }

        return expectedSum - actualSum;
    }
}

 

 

 

위 코드는 : 

 

• 배열의 길이 구하기:
  • n은 배열 nums의 길이를 저장합니다. 이 길이는 0부터 n까지의 숫자 중 하나가 빠져 있는 상태에서의 숫자 개수입니다.
• 예상 합 계산:
  • expectedSum은 0부터 n까지의 모든 숫자의 합을 계산한 값입니다. 이는 등차수열의 합 공식 n * (n + 1) / 2를 사용하여 계산됩니다.
  • 예를 들어, n이 3이라면 0 + 1 + 2 + 3 = 6이 됩니다.
• 실제 합 계산:
  • actualSum은 배열 nums에 있는 숫자들의 합을 저장합니다.
  • 배열의 각 숫자를 순회하면서 actualSum에 더해줍니다.
• 누락된 숫자 찾기:
  • 예상 합에서 실제 합을 빼면 누락된 숫자를 찾을 수 있습니다.
  • 이는 배열에서 누락된 숫자가 예상 합에서 실제 합만큼 차이 나기 때문입니다.

---

개선된 코드 전 후 코드들의 Runtime 결과