이 프로그램은 사용자가 입력한 배열에서 0부터 99 사이 범위에 존재하지 않는, 즉 누락된 값들을 찾아 화면에 표시합니다. 예를 들어 아래와 같은 입력이 주어지면 해당 범위 안에서 빠져 있는 숫자와 구간을 출력합니다.
입력 : array = {88, 105, 3, 2, 200, 0, 10};
출력 : 1 4-9 11-87 89-99
여기서 105와 200은 범위(0~99)를 벗어나므로 무시되며, 나머지 값들 사이에서 비어 있는 숫자들이 결과로 출력됩니다.
알고리즘
핵심 아이디어는 크기가 MAX(100)인 불리언(flag) 배열을 활용하는 것입니다. 입력 배열에 존재하는 값은 true로 표시하고, flag 배열에서 false로 남아 있는 인덱스가 바로 누락된 숫자입니다.
시작
1단계 -> 요소를 가진 배열을 준비하고, bool형 flag[MAX]를 false로 초기화하며, int형 i, j와 배열의 크기 n을 선언한다.
2단계 -> i를 0부터 n 미만까지 반복한다.
만약 array[i] < 100 && array[i] >= 0 이라면
flag[array[i]] = true 로 설정
조건문 종료
3단계 -> 반복문 종료
4단계 -> i를 0부터 MAX 미만까지 반복한다.
만약 flag[i] == false 라면
j = i + 1 로 설정
j < MAX && flag[j] == false 인 동안 반복
j++
반복 종료
만약 j == i + 1 이라면
i 출력 (연속되지 않은 단일 누락 숫자)
아니면
i 와 j-1 출력 (누락된 구간)
조건문 종료
i = j 로 설정
조건문 종료
5단계 -> 반복문 종료
종료
예제 코드
다음은 위 알고리즘을 C 언어로 구현한 전체 코드입니다.
#include <stdio.h>
#define MAX 100
int main(int argc, char const *argv[]) {
int array[] = {88, 105, 3, 2, 200, 0, 10};
bool flag[MAX] = { false }; //flag 배열의 모든 값을 false로 초기화
int i, j, n;
n = sizeof(array)/sizeof(array[0]);
for (i = 0; i < n; i++) {
if (array[i] < 100 && array[i]>=0) {
flag[array[i]] = true; //배열에 존재하는 요소의 값을 true로 표시하여, 누락된 값은 false로 유지
}
}
for (i = 0; i < MAX; ++i) {
if(flag[i] == false) { //false 값 검사
j = i+1; //다음 반복을 위한 값 설정
while(j<MAX && flag[j] == false) //flag[j]가 false인지 검사
j++;
if (j==i+1) //누락된 단일 숫자 출력
printf("%d\n", i);
else //누락된 범위 출력
printf("%d-%d\n", i, j-1);
i = j; //해당 숫자부터 다시 시작할 수 있도록 범위의 마지막 값으로 초기화
}
}
return 0;
}
실행 결과
위 프로그램을 실행하면 다음과 같은 결과가 출력됩니다.
1 4-9 11-87 89-99
동작 원리 정리
첫 번째 반복문에서는 입력 배열을 한 번 순회하면서 0 이상 100 미만인 값에 해당하는 flag 인덱스를 true로 변경합니다. 두 번째 반복문에서는 flag 배열을 처음부터 끝까지 확인하면서 false로 남아 있는 위치를 찾습니다. 이때 연속된 false 구간의 길이가 1이면 단일 숫자를, 2 이상이면 "시작값-끝값" 형태의 구간으로 출력합니다. 이 방식은 시간 복잡도 O(n + MAX)로 동작하므로 매우 효율적입니다.