C# 내장 함수 없이 정렬된 배열에서 누락된 숫자를 찾는 3가지 방법

코딩 테스트나 기술 면접에서 자주 등장하는 문제 중 하나가 바로 '정렬된 배열에서 누락된 숫자 찾기'입니다. C#에서는 LINQ 같은 내장 함수를 사용하지 않고도 여러 가지 방법으로 이 문제를 해결할 수 있습니다. 이 글에서는 세 가지 대표적인 접근 방식과 실제로 동작하는 예제 코드를 소개합니다.

세 가지 해결 방법

• 첫 번째 방법 – 합 공식 활용: 등차수열 합 공식 n(n+1)/2로 0부터 n까지의 기대 합계를 구한 뒤, 배열 요소의 실제 합을 빼면 누락된 숫자가 계산됩니다.

• 두 번째 방법 – 불리언 배열 활용: 배열 크기보다 1 큰 불리언 배열을 새로 만들고, 기존 배열을 순회하며 발견된 숫자의 위치를 true로 표시합니다. 이후 false로 남아 있는 인덱스가 곧 누락된 숫자입니다.

• 세 번째 방법 – XOR 연산 활용: 배타적 논리합(XOR)의 성질, 즉 같은 값을 두 번 XOR하면 0이 된다는 특징을 이용해 누락된 숫자를 도출합니다.

예제 코드

using System;
namespace ConsoleApplication {
    public class Arrays {
        // 방법 1: 합 공식 활용
        public int MissingNumber1(int[] arr) {
            int totalcount = 0;
            for (int i = 0; i < arr.Length; i++) {
                totalcount += arr[i];
            }
            int count = (arr.Length * (arr.Length + 1)) / 2;
            return count - totalcount;
        }
        // 방법 2: 불리언 배열 활용
        public int MissingNumber2(int[] arr) {
            bool[] tempArray = new bool[arr.Length + 1];
            int element = -1;
            for (int i = 0; i < arr.Length; i++) {
                int index = arr[i];
                tempArray[index] = true;
            }
            for (int i = 0; i < tempArray.Length; i++) {
                if (tempArray[i] == false) {
                    element = i;
                    break;
                }
            }
            return element;
        }
        // 방법 3: XOR 연산 활용
        public int MissingNumber3(int[] arr) {
            int result = 1;
            for (int i = 0; i < arr.Length; i++) {
                result = result ^ arr[i];
            }
            return result;
        }
    }
    class Program {
        static void Main(string[] args) {
            Arrays a = new Arrays();
            int[] arr = { 0, 1, 3, 4, 5 };
            Console.WriteLine(a.MissingNumber1(arr));
            Console.WriteLine(a.MissingNumber2(arr));
            Console.WriteLine(a.MissingNumber3(arr));
            Console.ReadLine();
        }
    }
}

실행 결과

2
2
2

배열 { 0, 1, 3, 4, 5 }에서 숫자 2가 빠져 있으므로, 세 가지 방법 모두 올바르게 2를 반환합니다.

각 방법의 동작 원리

1. 합 공식 방식

0부터 n까지 연속된 숫자의 합은 n(n+1)/2로 구할 수 있습니다(가우스 덧셈). 배열에 실제로 들어 있는 값들의 합을 이 이론값에서 빼면, 그 차이가 바로 빠진 숫자가 됩니다. 추가 메모리가 전혀 필요 없어 공간 복잡도가 O(1)이라는 장점이 있습니다.

2. 불리언 배열 방식

크기가 n+1인 bool 배열을 만들어 각 숫자의 존재 여부를 기록합니다. 배열을 한 번 순회하며 존재하는 숫자를 표시하고, 다시 순회하면서 false인 첫 번째 인덱스를 찾으면 그것이 누락된 숫자입니다. 로직이 직관적이고 디버깅이 쉽지만, O(n) 크기의 추가 메모리가 필요합니다.

3. XOR 연산 방식

XOR은 두 비트가 서로 다를 때만 1을 반환하며, a ^ a = 0, a ^ 0 = a라는 성질을 가집니다. 따라서 완전한 범위의 숫자들과 배열의 숫자들을 차례로 XOR하면 짝이 맞는 값들은 모두 0으로 사라지고 누락된 숫자만 남게 됩니다. 덧셈과 달리 오버플로 걱정이 없어 큰 수를 다룰 때 특히 유용합니다.

방법별 비교

참고로 위 세 가지 방법은 배열이 정렬되어 있지 않더라도 동일하게 작동합니다. 메모리 효율과 안정성을 고려하면 XOR 연산 방식이 가장 널리 권장되며, 코드의 가독성이 더 중요하다면 합 공식 방식이 좋은 선택이 될 수 있습니다.