[99클럽 코테 스터디] 29일차 TIL - Missing Number

오늘의 학습 키워드

</> 이분탐색

공부한 내용 본인의 언어로 정리하기

class Solution {
    public int missingNumber(int[] nums) {
        Arrays.sort(nums);

        for(int i = 0; i < nums.length; i++){
            if(nums[i] != i){
                return i;
            }
        }
        return nums.length;
    }
}

오늘의 회고

오늘 문제는 이분탐색의 주제로 배열에서 누락된 값을 찾아내는 문제였다.
n이 nums.length이고 그 숫자중 누락된 값을 찾는것이면 오름차순으로 정렬한 후에 어차피 시작은 0 부터이니까 인덱스 시작 값과 같으므로 nums의 길이만큼 반복하며 nums[i]와 i가 같지않은 값만 반환해주면 되는 문제였다.
8분만에 문제를 제출하고 더 효율적인 방법이 있을 것 같아서 한가지 방법으로 더 풀어보려고 한다.

---

일단 이진 탐색 / 이분 탐색에 대해서 먼저 알아보도록 하자.

이진 탐색 알고리즘이란 정렬되어 있는 배열에서 찾고자 하는 특정한 값을 찾아내는 알고리즘이다.
이진 탐색 알고리즘이 탐색하는 방식은 배열의 중간에 있는 값을 선택하여 찾고자하는 값과 비교한다.
찾고자하는 값이 중간 값보다 작으면 중간 값을 기준으로 왼쪽으로 다시 탐색, 크다면 오른쪽으로 다시 탐색한다.
다시 탐색을 시작할 때 찾고자하는 값이 중간 값보다 작으면 해당 중간 값부터 우측 끝값을 제거하고 다시 중간 값을 선택하고 찾고하자는 값을 찾는다.
찾고자 하는 값과 중간 값이 일치할 때 까지 이 과정을 반복한다.

❗ 만약 low값보다 high값이 작다면 더 이상 검색할 범위가 없어 검색 실패로 종료된다.

이진 탐색 과정

중간 값을 구하는 식은 이러하다.

mid(중간 값) = low + (high - low) / 2

이렇게 중간 값을 구했으니 설명했다 싶이 중간 값을 기준으로 양 옆을 탐색해서 누락된 위치의 수를 찾으면 되겠다.

배열이 순서대로 되어있어야 작동하므로 똑같이 오름차순 정렬부터 시켜준다.

Arrays.sort(nums);

필요한 값인 low와 high를 초기화 시켜준다.

int low = 0;
int high = nums.length - 1;

nums.length - 1인 이유는 예를 들어 배열의 길이가 9인 경우 low가 0부터 시작해 9개일 경우 high는 8이기 때문이다.

초기화를 해주었으니 아까 설명대로 low가 high보다 크면 안되므로 조건을 걸어주고 반복을 해준다.

while(low <= high){
}

이제 반복문 안에 중간 값을 구해서 그 값과 양 옆의 값을 순서에 맞게 구한다. 아래 코드는 반복문 안에 들어가는 내용이다.

int mid = low + (high - low) / 2;

if(nums[mid] == mid){
	low = mid + 1;
} else {
	high = mid - 1;
}

반복하다보면 마지막에는 low의 값이 최종 누락된 숫자의 위치가 되므로 반환해준다.

return low;

예시로 nums[]가 [9,6,4,2,3,5,7,0,1] 라고 가정하면 위의 코드대로 진행을 해보겠다.
오름차순 배열을 하면 [0,1,2,3,4,5,6,7,9]이다 .
여기서 low는 0 high는 8로 초기화가 되게 된다.
그리고 중간 값을 구하는 식에 따라 mid는 4로 시작을 하게 된다.

이제 low가 high보다 커지기 전까지만 반복을 해준다.
중간 값이 인덱스와 같다면 누락된 값을 오른쪽에 존재하게 된다. 이유는 nums[mid]가 mid와 같다는 것은 모든 숫자가 [0,1,2,3,4]처럼 순서대로 배치되어 있기 때문에 만약 누락된 숫자가 0부터 mid까지의 범위에 있다면 그 누락된 숫자는 이 범위에서 확인되지 않아야 한다.

반대로 중간 값이 인덱스와 다른 경우에는 배열의 왼쪽 절반에 누락된 숫자가 존재할 수 있다는 것을 의미합니다.

일치한다면 오른쪽 값을 탐색해야 하므로 mid값에 +1을 하여서 오른쪽값을 점점 탐색해가게 되고 반대의 경우 -1을 해서 왼쪽의 값을 탐색하게 된다. 값을 더하고 빼는 이유는 탐색 범위를 점점 좁혀나가기 위함이다.

최종적으로 low값이 누락된 값이 되는 이유는 탐색 중 low와 high를 조정함으로써 누락된 숫자가 존재할 범위를 계속 좁혀나가고 low는 반복 종료 시점에서 누락된 숫자가 있어야 할 인덱스가 된다. 탐색 범위의 축소 과정에서 누락된 숫자가 포함될 위치가 low로 결정되기 때문이다. 실행되는 제한사항을 보면 low와 high가 같아지거나 low와 high를 초과할 때까지 진행이 된다.

AI 코드리뷰

현재 코드의 장점

1. 이진 탐색 사용: 이진 탐색을 사용하여 O(log n) 시간 복잡도로 문제를 해결하고 있습니다. 이는 매우 효율적인 접근 방법입니다.
2. 정확한 결과: 수학적인 계산을 정확하게 수행하며, 이진 탐색의 조건을 잘 설정하여 올바른 결과를 제공합니다.

현재 코드의 단점

1. 변수 타입: long 타입을 사용하여 계산하고 int로 캐스팅하여 반환합니다. 이 문제에서 int로도 충분하지만, long 타입을 사용하는 이유가 필요하지 않을 수 있습니다.
2. 계산의 안전성: 이진 탐색의 로직은 잘 작성되었지만, low와 high 값이 int 범위를 초과하는 경우를 고려하지 않았습니다.

시간 복잡도

• 정렬 단계: Arrays.sort(nums)는 O(n log n)의 시간 복잡도를 가집니다.
• 탐색 단계: for 루프는 배열을 한 번 순회하므로 O(n)의 시간 복잡도를 가집니다.

이분 탐색 풀이 리뷰

class Solution {
    public int missingNumber(int[] nums) {
        Arrays.sort(nums);

        int low = 0;
        int high = nums.length - 1;

        // 이진 탐색을 시작합니다.
        while (low <= high) {
            int mid = low + (high - low) / 2;
            
            // 배열의 중간 값과 인덱스를 비교합니다.
            if (nums[mid] == mid) {
                // 중간 값이 인덱스와 같으면 누락된 숫자가 오른쪽에 있습니다.
                low = mid + 1;
            } else {
                // 중간 값이 인덱스와 다르면 누락된 숫자가 왼쪽에 있습니다.
                high = mid - 1;
            }
        }

        // 최종적으로 low가 누락된 숫자의 위치가 됩니다.
        return low;
    }
}

개선된 버전의 장점

1. 효율적인 탐색: 이진 탐색을 사용하여 누락된 숫자를 찾기 때문에, 탐색 부분의 시간 복잡도가 O(log n)으로 매우 효율적입니다.
2. 정렬된 배열에 적합: 정렬된 배열에서 특정 조건을 만족하는 값을 찾는 데 적합한 방법입니다. 이 경우에도 배열이 정렬된 상태에서 누락된 숫자를 빠르게 찾을 수 있습니다.
3. 공간 효율성: 이 알고리즘은 O(1)의 추가 공간만 사용하므로, 공간 효율성이 뛰어납니다.

개선된 버전의 단점

1. 사전 정렬 필요: 배열을 이진 탐색하기 전에 정렬해야 하므로, 배열 정렬에 O(n log n)의 시간이 소요됩니다. 이로 인해 전체 시간 복잡도가 이진 탐색 자체의 O(log n)보다 커지게 됩니다.
2. 추가 정렬 과정: 만약 배열이 이미 정렬되어 있지 않다면, 추가적인 정렬 과정이 필요하므로 비효율적일 수 있습니다. 정렬 과정이 전체 성능을 저하시킬 수 있습니다.
3. 정렬이 불필요한 경우: 만약 입력이 이미 특정 순서대로 정렬되어 있거나, 다른 방법으로 누락된 숫자를 찾을 수 있는 경우, 정렬 자체가 불필요할 수 있습니다.
   

시간 복잡도

• 정렬 단계: Arrays.sort(nums)는 O(n log n)의 시간 복잡도를 가집니다.
• 이진 탐색 단계: 이진 탐색의 시간 복잡도는 O(log n)입니다.

---

내일 공부할 것 :

이분탐색 알고리즘에 대해서 정리해서 올려야겠다.

문제

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