[자바] Leetcode 268 - Missing Number

문제

배열 nums가 주어지는데, 이때 배열에는 범위 [0,n]에 속하는 n개의 숫자가 담겨있다. 범위가 [0,n]이라면 총 n-1개의 숫자가 있어야하는데, n개만 담겨있다는 건 숫자 한개가 빠져있다는 뜻. 빠진 숫자를 반환하는 문제다.

leetcode.com/problems/missing-number/

Missing Number - LeetCode

 

첫 번째 Solution

쉽게 생각했다. 길이 n을 가지는 boolean 배열을 만들고, 배열 nums를 탐색하면서 boolean 배열에 visited(=배열에 숫자가 나왔는지) 여부를 체크한다. 그리고 나서 boolean 배열을 다시 탐색하면서 false로 남아있는 숫자를 발견하면 int answer 변수에 담고 바로 return 해버린다.

기존 배열 nums를 탐색하는데 O(n) + boolean 배열을 탐색하는데 최대 O(n) 이기 때문에 최종 시간 복잡도도  O(n)밖에 안 걸린다. 하지만, 배열을 하나 더 만들어야 하기 때문에 공간복잡도가 O(n)이다. 

class Solution {
    public int missingNumber(int[] nums) {
        int answer = 0;
        
        int len = nums.length;
        
        boolean[] contained = new boolean[len+1];
        
        for(int i=0;i<len;i++){
            contained[nums[i]] = true;
        }
        
        for(int i=0;i<=len;i++){
            if(!contained[i]) {
                answer = i;
                break;
            }
        }
        
        return answer;
    }
}

 

두 번째 Solution

아래 링크에서 참고했다.

XOR 연산자의 성격을 활용한 풀이법인데, 시간복잡도 O(n)에 공간복잡도도 O(1)이다.

근데 내가 아직 이해를 잘 못하겠다. A^B^B=A인 점을 이용해서 짠 코드라고 하는데, 고민이 더 필요하다.

leetcode.com/problems/missing-number/discuss/69786/3-different-ideas%3A-XOR-SUM-Binary-Search.-Java-code

3 different ideas: XOR, SUM, Binary Search. Java code - LeetCode Discuss

세 번째 Solution

간단한 수학식을 이용한 풀이법이다!

n이 굉장히 클 때에는 overflow가 날 수도 있다고 하지만, 일단 문제 내에서는 1<=n<=10000라는 조건이 있으니까 이 풀이법도 적용가능하다. Overflow 걱정 없이 해결하려면 두 번째 Solution을 적용하는 게 맞을 것 같다.

 

0부터 n까지의 총합을 구한다고 했을 때, 실제로 나와야 하는 값을 계산해 놓고 (변수 sum), 배열 nums를 탐색하면서 sum에서 num[i]의 값을 빼간다. 그렇게 되면 배열을 다 돌았을 때 최종적으로 정해지는 sum의 값이 빠진 숫자가 되는 것!

 

나는 이 풀이법이 첫 번째 풀이법보다 훨씬 낫다고 생각했는데, Runtime이나 Memory 측면에서 모두 첫번째 풀이법보다 안 좋게 나왔다. 이유가 뭘까?

class Solution {
    public int missingNumber(int[] nums) {
        
        int len = nums.length;
        int sum = ((len+1)*len)/2;
        
        for(int i=0;i<len;i++){
            sum -= nums[i];
        }
        return sum;
    }
}