배열에 저장된 값 중에서 연속된 숫자 시퀀스를 기준으로 빠져 있는 숫자(누락된 숫자)를 찾아야 하는 경우가 생각보다 많습니다. 예를 들어 배열이 [6, 7, 9]라면, 1부터 시작하는 연속된 수열의 관점에서 볼 때 1, 2, 3, 4, 5가 모두 빠져 있는 셈입니다. 이번 글에서는 PHP로 이런 누락된 숫자를 찾아 출력하는 프로그램을 예제와 함께 살펴보겠습니다.
예제 코드
<?php
function missing_nums($my_arr, $arr_len, $val)
{
sort($my_arr); // 배열을 오름차순으로 정렬
$i = 0;
// 0 이하의 값은 건너뛰고 양수부터 검사
while ($i < $arr_len && $my_arr[$i] <= 0)
$i++;
$count = 0; // 지금까지 찾은 누락 숫자의 개수
$current_num = 1; // 현재 확인 중인 숫자
while ($count < $val && $i < $arr_len)
{
if ($my_arr[$i] != $current_num)
{
echo $current_num , " "; // 누락된 숫자 출력
$count++;
}
else
$i++; // 배열의 다음 요소로 이동
$current_num++;
}
// 배열 검사가 끝난 뒤에도 개수가 부족하면 이어서 출력
while ($count < $val)
{
echo $current_num , " ";
$current_num++;
$count++;
}
}
$my_arr = array(6, 7, 9);
$arr_len = sizeof($my_arr);
$val = 5;
print_r("The missing numbers in the array is ");
missing_nums($my_arr, $arr_len, $val);
?>
실행 결과
The missing numbers in the array is 1 2 3 4 5
코드 동작 원리
missing_nums() 함수는 연속된 숫자로 이루어진 배열에서 어떤 값이 빠져 있는지 확인하는 역할을 합니다. 동작 과정을 단계별로 정리하면 다음과 같습니다.
- 정렬: sort() 함수로 배열을 오름차순 정렬해 작은 숫자부터 차례대로 비교할 수 있도록 준비합니다.
- 변수 초기화: 배열 인덱스($i), 지금까지 찾은 누락 숫자의 개수($count), 현재 확인 중인 숫자($current_num)를 각각 초기화합니다.
- 누락 여부 판별: 첫 번째 while 루프에서 배열의 현재 요소와 $current_num을 비교합니다. 두 값이 일치하지 않으면 해당 숫자가 배열에 없다는 뜻이므로 화면에 출력하고 $count를 1 증가시킵니다. 값이 일치하면 배열 인덱스만 앞으로 이동합니다.
- 나머지 숫자 처리: 배열의 모든 요소를 검사한 후에도 요청한 개수($val)만큼 찾지 못했다면, 두 번째 while 루프가 마지막 요소 다음 숫자부터 연속해서 출력합니다.
함수 호출과 결과 출력
함수 외부에서는 먼저 대상 배열을 정의하고, sizeof() 함수로 배열의 길이를 변수에 저장합니다. 그리고 찾으려는 누락 숫자의 개수도 함께 지정한 뒤, 이 세 값을 매개변수로 넘겨 missing_nums() 함수를 호출합니다. 함수가 계산한 결과는 최종적으로 콘솔에 출력됩니다.
위 예제에서는 배열 [6, 7, 9]에서 5개의 누락된 숫자를 찾도록 설정했기 때문에, 1부터 시작해 배열에 없는 1, 2, 3, 4, 5가 순서대로 출력됩니다. 이 알고리즘은 정렬 단계에서 O(n log n), 비교 단계에서 O(n + k)(k는 찾을 누락 숫자의 개수)의 시간 복잡도를 가지므로 중간 크기의 배열에서도 효율적으로 동작합니다.