[Algorithm] Codility_PermMissingElem in Java

💡 Codility Easy_PermMissingElem:

1부터 N + 1까지 주어진 배열에서 빠진 요소 찾기

🌱 코드 in Java

알고리즘: Binary Search

import java.util.*;

class Solution {
    public int solution(int[] A) {
        int len = A.length;

        if (len == 0) // 빈 배열일 경우
            return 1;
        else if (len == 1) // 1개만 들어올 경우
            return A[0] != 1 ? 1 : 2;
        
        Arrays.sort(A); // Binary Search를 위한 정렬
        int left = 0, right = len - 1;

        while (left <= right) {
            int mid = (left + right) / 2;
            if (A[mid] != mid + 1) // 빠진 요소가 좌측에 있을 경우
                right = mid - 1;
            else // 빠진 요소가 우측에 있을 경우
                left = mid + 1;
        }
        return left + 1; // left idx + 1 => 빠진 요소
    }
}

이번 문제는 Easy~ 여서 그런지 쉽게 풀었다. 딱 1개 요소만 빠져있기 때문에 index로 비교하면 좋을 것 같다는 생각이 들었고, 이진 탐색을 하면 효율적으로 탐색이 가능하다고 생각했다.

그런데 첫트 실패. 왜? 빈배열과 1개만 들어오는 경우를 고려하지 않아서..

다 풀고나서 다른 풀이를 찾아본 것 중에 가장 신박했던 것은
1 ~ N까지의 자연수의 합을 구하는 공식을 대입해서 푼 방법이었다.
결국에는 1 ~ (N + 1)까지의 자연수의 합에서 주어진 배열의 합을 빼면 빠진 요소가 나오는 것이다..
이런 생각 진짜 어케함. 다 천재들임; 이래서 수학을 공부해야 하나봐..

class Solution {
    public int solution(int[] A) {
        long n = A.length + 1; // n + 1개로 가정
        long sum = n * (n + 1) / 2; // 1 ~ n까지의 자연수의 합 feat.가우스
        
        for (int i = 0; i < n - 1; i++)
            sum -= A[i]; // 어차피 배열의 합을 구한다음에 뺄거라면 그냥 sum에서 빼도 동일하니까

        return (int) sum;
    }
}

이 방식은 sum이 int형일 경우 overflow가 발생할 수 있으니 주의해야하는 것을 빼면,
정렬 과정이 없기 때문에 시간복잡도가 O(n)이다.

대박쓰.

🧠 기억하자

1. 예외 조건을 잘 기억하자

2. OverFlow 조심