배열에 들어 있지 않은 가장 작은 양의 정수부터 차례대로 'n'개를 찾아야 하는 문제는 코딩 테스트에서도 자주 등장합니다. 예를 들어 배열이 [6, 8, 0]이라면 0은 대상에서 제외되고, 1부터 5까지의 숫자가 배열에 없으므로 이것들이 누락된 숫자가 됩니다. 이 글에서는 PHP로 이 문제를 해결하는 방법을 예제 코드와 함께 자세히 살펴보겠습니다.
예제 코드
<?php
function missing_values($my_arr, $len, $n){
// 배열을 오름차순으로 정렬
sort($my_arr);
$i = 0;
// 0 이하의 값은 건너뜀
while ($i < $len && $my_arr[$i] <= 0)
$i++;
$count = 0;
$curr = 1;
// 배열 범위 안에서 누락된 숫자 찾기
while ($count < $n && $i < $len){
if ($my_arr[$i] != $curr){
echo $curr . " ";
$count++;
}
else
$i++;
$curr++;
}
// 배열이 끝나도 모자란 만큼 계속 출력
while ($count < $n){
echo $curr . " ";
$curr++;
$count++;
}
}
$my_arr = array(6, 8, 0);
$len = sizeof($my_arr);
$n = 5;
print_r("배열에서 누락된 값: ");
missing_values($my_arr, $len, $n);
?>
실행 결과
배열에서 누락된 값: 1 2 3 4 5
코드 동작 원리
1. 배열 정렬
missing_values 함수는 배열, 배열의 길이, 그리고 찾고자 하는 누락 숫자의 개수 n을 매개변수로 받습니다. 함수가 시작되면 sort() 함수로 배열을 오름차순 정렬하여 작은 값부터 순서대로 비교할 수 있도록 준비합니다.
2. 0 이하 값 건너뛰기
찾으려는 숫자는 1부터 시작하는 양의 정수이므로, 0 이하의 값은 탐색 대상에서 제외합니다. 인덱스 $i를 앞으로 이동시켜 0보다 큰 첫 번째 요소부터 비교를 시작합니다.
3. 누락된 숫자 탐색
$count는 지금까지 찾은 누락 숫자의 개수를, $curr은 현재 확인 중인 숫자를 의미하며 각각 0과 1로 초기화됩니다. 이후 $count가 n에 도달하거나 배열의 끝에 도달할 때까지 아래 규칙으로 비교를 반복합니다.
- 배열 요소가 $curr과 같은 경우: 해당 숫자는 배열에 이미 존재하므로 $i를 증가시켜 다음 배열 요소로 넘어갑니다.
- 배열 요소가 $curr과 다른 경우: $curr은 배열에 없는 숫자이므로 화면에 출력하고 $count를 1 증가시킵니다.
매 반복이 끝날 때마다 $curr도 함께 증가합니다.
4. 배열이 끝난 후 마무리 처리
배열의 모든 요소를 확인한 후에도 찾은 누락 숫자의 개수가 n보다 적다면, 마지막 while 루프가 부족한 만큼의 숫자를 이어서 출력합니다. 예제 배열의 양수 최솟값이 6이므로 1부터 5까지 모두 누락된 숫자가 되어 한 번에 출력됩니다.
실행부 살펴보기
함수 외부에서는 배열 [6, 8, 0]을 정의하고, sizeof() 함수로 배열의 길이를 구해 $len에 저장합니다. 찾고자 하는 누락 숫자의 개수 $n은 5로 설정했습니다. 이 세 값을 매개변수로 전달해 함수를 호출하면 결과가 화면에 출력됩니다.
마무리
이 알고리즘은 배열을 한 번 정렬한 뒤 선형 탐색으로 누락된 숫자를 찾기 때문에 구현이 간단하고 직관적입니다. 시간 복잡도는 정렬 과정을 포함해 O(n log n) 수준이며, 별도의 추가 메모리 없이 문제를 해결할 수 있다는 장점이 있습니다.