[99클럽 코테 스터디] 29일차 TIL 이분탐색

 

 

오늘의 문제는 LeetCode

 

268. Missing Number

 

 

문제

 

 

 

문제 설명 

정수형 배열 nums가 주어집니다. nums는 0부터 n까지의 서로 다른 숫자를 포함합니다. 이 때 배열에서 누락된 숫자를 반환하면 됩니다. 

예를 들어 nums = [3,0,1] 일 때 [0,3] 범위의 숫자가 배열에 포함되어 있어야 하는데 2가 없으므로 2를 반환하면 됩니다. 

 

 

 

문제 풀이 시간 

권장 풀이 시간은 60분이었고, 저는 18분이 걸렸습니다.

 

 

 

문제 접근 방식

주어진 배열 nums를 오름차순 정렬합니다. 정렬된 배열에서 마지막 요소를 배열의 최대값으로 설정합니다. 이후 배열의 길이와 최대값을 비교하여 최대값이 배열의 길이와 다를 경우, 최대값이 배열 내에 없다는 것을 의미하므로 배열의 길이를 반환합니다. 

while문을 사용해 배열의 요소를 0 부터 n까지 들어있는지 하나씩 확인합니다. 만약 배열 내에 해당 값이 없을 경우, 그 값을 반환합니다. 

 

 

 

문제 풀이

import java.util.*;

class Solution {
    public int missingNumber(int[] nums) {

        Arrays.sort(nums); 

        int len = nums.length;
        int max = nums[len - 1];
        int answer = 0; 
        boolean isMissing = false; 

        if(max != len) {
            return len; 
        }
        
        while(!isMissing) {
            if(nums[answer] != answer) {
                isMissing = true; 
                return answer;
            } else {
                answer++;
            }
        }
        
        return answer;
    }
}

 

 

코드 개선하기 

배열을 오름차순 정렬한 부분을 제거함으로써 시간 복잡도를 O(n log n)에서 O(n)으로 줄일 수 있습니다.

또한 최대값을 배열의 길이와 비교하여 길이가 다를 경우 len을 반환하는 방식 대신, 배열의 전체 합을 계산한 후 빠진 숫자를 찾아 반환하는 방법을 사용하면 배열을 정렬하지 않아도 누락된 숫자를 효율적으로 찾을 수 있습니다.

이 과정에서 논리형 변수 isMissing을 사용하지 않고도 문제를 해결할 수 있기 때문에 이 부분도 제거합니다. 

import java.util.*;

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

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

        return sum - arrSum;
    }
}

 

 

 

 

 

 

 

 

이렇게 오늘 29일차 TIL을 작성해 보았습니다.