Make Array Consecutive 2

주어진 정수 배열을 정렬하고, 배열 안의 연속된 숫자 사이에 빈 공간이 있을 때, 이 빈 공간을 채우기 위해 필요한 추가적인 숫자의 개수를 구하는 문제입니다.

예를 들어, 주어진 배열이 [6, 2, 3, 8]이라면, 이 배열을 정렬하면 [2, 3, 6, 8]이 됩니다. 그런데 3 다음에 4와 5가 빈 공간으로 존재하고, 6과 8사이에 7의 빈 공간이 존재하므로,  최소 3개의 추가 숫자가 필요합니다.

따라서 이 문제는 정렬된 배열에서 숫자들 사이의 갭을 계산하여 필요한 추가 숫자의 수를 구하는 것이 목표입니다.

 

int solution(int[] statues) {
    Array.Sort(statues);
    int start = statues[0];
    int cnt = 0;
    int idx = 1;
    for(int i = (start+1);i<=statues[statues.Length-1];i++){
        if(idx >= statues.Length) break;
        if(statues[idx] != i){
            cnt++;
        }
        else{
            idx++;
        }
    }
    return cnt;
}

 

Array.Sort(statues): 입력 배열 statues를 오름차순으로 정렬합니다.
int start = statues[0];: 정렬된 배열에서 가장 작은 값인 첫 번째 원소를 start에 저장합니다.
int cnt = 0;: 추가해야 할 숫자의 개수를 나타내는 변수 cnt를 초기화합니다.
int idx = 1;: 배열을 탐색하기 위한 인덱스 변수 idx를 초기화합니다.
그 후, for 루프에서 start 다음부터 statues 배열의 가장 큰 값까지 순회하면서 빈 공간을 찾습니다.

if (statues[idx] != i): 만약 현재 인덱스 idx가 배열의 범위를 벗어나지 않았고, 현재 값이 i와 같지 않다면 (빈 공간이라면), cnt를 증가시킵니다.
else: 현재 값이 i와 같다면, idx를 증가시켜서 다음 값을 비교합니다.
루프를 마치면 최소로 필요한 추가 숫자의 개수인 cnt를 반환합니다.

정렬 후에 배열을 한 번 순회하는 방식을 사용하고 있습니다.