개요
C#에서 LINQ나 기타 내장 함수를 사용하지 않고, 정렬된 배열 안에서 누락된 숫자(missing number)와 반복되는 숫자(repeating number)를 찾는 방법을 소개합니다. 핵심 아이디어는 배열의 값을 인덱스로 활용하는 보조 배열(마커 배열)을 만드는 것입니다.
누락된 숫자 찾기
원본 배열보다 크기가 1 큰 불리언(bool) 배열을 새로 생성합니다. 원본 배열을 처음부터 끝까지 순회하면서, 발견된 숫자를 인덱스로 삼아 새 배열의 해당 위치를 true로 표시합니다. 이후 새 배열을 다시 순회하여 처음으로 false인 인덱스를 찾으면, 그 인덱스 값이 곧 누락된 숫자입니다.
반복되는 숫자 찾기
같은 방식으로 크기가 1 더 큰 정수(int) 배열을 생성합니다. 원본 배열을 순회하면서 각 숫자의 등장 횟수를 기록하는데, 처음 등장한 숫자는 1로, 두 번째로 등장한 숫자는 2로 표시합니다. 이 배열을 순회하여 값이 2인 첫 번째 인덱스를 찾으면, 그것이 반복되는 숫자입니다.
전체 예제 코드
using System;
namespace ConsoleApplication{
public class Arrays{
public void MissingNumberAndRepeatedNumber(int[] arr){
// 누락된 숫자 확인용 불리언 배열
bool[] tempArray = new bool[arr.Length + 1];
int missingelement = -1;
int repeatingelement = -1;
for (int i = 0; i < arr.Length; i++){
int index = arr[i];
if (!tempArray[index]){
tempArray[index] = true;
}
};
// false인 첫 번째 인덱스 = 누락된 숫자
for (int i = 0; i < tempArray.Length; i++){
if (!tempArray[i]){
missingelement = i;
break;
}
}
// 반복 횟수 확인용 정수 배열
int[] tempArray1 = new int[arr.Length + 1];
for (int i = 0; i < arr.Length; i++){
int index = arr[i];
if (tempArray1[index] == 0){
tempArray1[index] = 1;
}else if (tempArray1[index] == 1){
tempArray1[index] = 2;
}
};
// 값이 2인 첫 번째 인덱스 = 반복되는 숫자
for (int i = 0; i < tempArray1.Length; i++){
if (tempArray1[i] == 2){
repeatingelement = i;
break;
}
}
Console.WriteLine(missingelement);
Console.WriteLine(repeatingelement);
}
}
class Program{
static void Main(string[] args){
Arrays a = new Arrays();
int[] arr = { 0, 1, 1, 3, 4 };
a.MissingNumberAndRepeatedNumber(arr);
Console.ReadLine();
}
}
}출력 결과
2 1
동작 원리 살펴보기
입력 배열이 { 0, 1, 1, 3, 4 }일 때의 실행 과정은 다음과 같습니다.
- 누락된 숫자: 불리언 배열에서 인덱스 0, 1, 3, 4는
true로 표시되지만, 인덱스 2만false로 남습니다. 따라서 누락된 숫자는 2입니다. - 반복되는 숫자: 정수 배열에서 값 1은 두 번 등장하므로 해당 인덱스의 값이 2가 됩니다. 따라서 반복되는 숫자는 1입니다.
복잡도 분석
이 알고리즘은 배열을 상수 번 순회하므로 시간 복잡도는 O(n)입니다. 추가로 두 개의 보조 배열을 사용하므로 공간 복잡도 역시 O(n)입니다. 내장 검색·정렬 함수에 의존하지 않으면서도 선형 시간 안에 두 값을 모두 구할 수 있는 것이 이 방법의 장점입니다.