[코테]코딜리티 - PermMissingElem

문제

문제 요약

• 각각 다른 정수로 구성된 배열 A가 매개변수로 주어짐.
• A는 1 ~ N+1의 범위를 가짐.
• 범위 내에서 연속된 숫자 중 오직 하나의 요소가 빠져있음.
• 배열에서 빠진 요소를 찾아서 반환해야함.
• N의 범위는 0~100,000.
• 배열의 모든 요소는 각각 다른 요소.
• 각 요소의 범위는 1~N+1의 범위를 가짐.

문제 분석

다음과 같이 문제를 분석하였다.

• 배열의 요소는 1부터 N+1이므로 반복문의 인덱스를 i(0) + 1로 가져가야함.
• 배열을 순회하기전 오름차순으로 정렬.
• 반복문을 돌면서 A[index]와 i + 1을 비교.
• 일치하지 않는 수치가 있다면 i + 1을 반환.
• 반복문이 정상적으로 종료된다면 N + 1이 없는 것이므로 배열의 길이 + 1을 반환.

여기서 시간복잡도를 보면 정렬을 할 경우 시간복잡도는 O(nlog n)이다. 즉, 배열의 길이가 100,000인 경우에는 100,000 log2(100,000) = 1,000,000이다. 이후 반복문이 O(n)의 시간복잡도를 가지기 때문에 O(100,000)이므로, 총 시간복잡도는 O(1,100,000)이라고 볼 수 있다.

위와 같은 계산을 통해 반복문과 정렬을 정상 수행하여도 적절하다고 판단하였다.

슈도 코드

배열 정렬

for(A의 길이만큼){
	if(A의 요소와 비교값을 틀리다면){
    	return 비교값;
    }
}

반복문이 정상 종료되면
return 배열의 길이 + 1을 반환

구현 코드

import java.util.Arrays;

class Solution {
    public int solution(int[] A) {
        Arrays.sort(A);

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

        return A.length + 1;
    }
}