이 튜토리얼에서는 자연수에서 일부 정수를 제거한 이후 남아 있는 수 중에서 K번째로 작은 값을 찾는 프로그램을 C++로 작성해 보겠습니다.
문제 개요
정수 배열 하나와 값 k가 주어집니다. 자연수 중에서 주어진 배열에 포함된 모든 숫자를 제거하고, 남은 자연수들 가운데 k번째로 작은 수를 구하는 것이 목표입니다.
예를 들어 배열이 {3, 5}이고 k = 2라고 가정해 봅시다. 자연수 1, 2, 3, 4, 5... 중에서 3과 5를 제거하면 1, 2, 4, 6, 7...이 남습니다. 이때 두 번째로 작은 수는 2입니다.
해결 접근 방식
문제를 해결하는 단계는 다음과 같습니다.
- 배열과 k값을 초기화합니다.
- 플래그 배열을 만들고, 주어진 배열에 존재하는 원소에 해당하는 인덱스만 1로 표시하고 나머지는 모두 0으로 초기화합니다.
- 1부터 시작하는 반복문을 돌며 아래 로직을 수행합니다.
- 현재 숫자가 제거 대상이 아니라면 k값을 1씩 감소시킵니다.
- k가 0이 되는 순간의 현재 값을 결과로 반환합니다.
- 반복문이 끝날 때까지 k가 0이 되지 않으면 0을 반환합니다.
구현 예제
위 알고리즘을 코드로 구현한 내용은 다음과 같습니다.
#include <bits/stdc++.h>
#define MAX 1000000
using namespace std;
int smallestNumber(int arr[], int n, int k) {
int flag[MAX];
memset(flag, 0, sizeof flag);
// 제거해야 할 숫자들을 플래그 배열에 표시
for (int i = 0; i < n; i++) {
flag[arr[i]] = 1;
}
// 자연수를 순회하며 k번째로 작은 수 탐색
for (int i = 1; i < MAX; i++) {
if (flag[i] != 1) {
k--;
}
if (!k) {
return i;
}
}
return 0;
}
int main() {
int k = 2;
int arr[] = { 3, 5 };
cout << smallestNumber(arr, 2, k) << endl;
return 0;
}실행 결과
위 코드를 실행하면 다음과 같은 출력을 확인할 수 있습니다.
2
시간 및 공간 복잡도 분석
이 알고리즘의 시간 복잡도는 O(n + MAX)이며, 여기서 n은 입력 배열의 크기, MAX는 탐색 범위의 상한입니다. 공간 복잡도는 O(MAX)로, 플래그 배열에 의해 결정됩니다.
배열의 크기나 k값이 매우 커질 경우 MAX 상수를 적절히 조정하거나, 정렬 기반 이분 탐색 방식으로 최적화할 수도 있습니다.
마무리
이 튜토리얼에 대해 궁금한 점이 있다면 댓글로 남겨주세요.