C# 시퀀스에서 누락된 숫자 찾는 방법

C#에서 정렬되지 않은 숫자 목록이 주어졌을 때, 최솟값과 최댓값 사이에 존재하지 않는 숫자(누락된 숫자)를 찾아야 하는 경우가 자주 있습니다. 이 글에서는 LINQ의 Enumerable.Range와 Except 메서드를 활용하여 간단하고 효율적으로 누락된 숫자를 찾는 방법을 알아보겠습니다.

1단계: 숫자 목록 생성하기

먼저 확인할 숫자들이 담긴 리스트를 만듭니다.

List<int> myList = new List<int>(){1, 2, 3, 5, 8, 9};

2단계: 최솟값과 최댓값 구하기

LINQ의 OrderBy를 사용해 리스트를 정렬한 뒤, First()와 Last()로 첫 번째(최솟값)와 마지막(최댓값) 요소를 가져옵니다.

int a = myList.OrderBy(x => x).First(); // 최솟값: 1
int b = myList.OrderBy(x => x).Last();  // 최댓값: 9

3단계: 전체 범위 생성 후 Except로 차집합 계산하기

Enumerable.Range(a, b - a + 1)로 최솟값부터 최댓값까지의 연속된 모든 숫자를 포함하는 새로운 리스트를 만듭니다. 그다음 Except 메서드로 원본 리스트에 없는 숫자, 즉 누락된 숫자만 추출합니다.

List<int> myList2 = Enumerable.Range(a, b - a + 1).ToList();
List<int> remaining = myList2.Except(myList).ToList();

전체 예제 코드

지금까지의 과정을 하나의 완성된 프로그램으로 정리하면 다음과 같습니다.

using System.Collections.Generic;
using System;
using System.Linq;

public class Program {
    public static void Main() {
        List<int> myList = new List<int>(){1, 2, 3, 5, 8, 9};
        Console.WriteLine("Numbers... ");
        foreach(int val in myList) {
            Console.WriteLine(val);
        }
        int a = myList.OrderBy(x => x).First();
        int b = myList.OrderBy(x => x).Last();
        List<int> myList2 = Enumerable.Range(a, b - a + 1).ToList();
        List<int> remaining = myList2.Except(myList).ToList();
        Console.WriteLine("Remaining numbers... ");
        foreach (int res in remaining) {
            Console.WriteLine(res);
        }
    }
}

실행 결과

Numbers...
1
2
3
5
8
9
Remaining numbers...
4
6
7

정리

이 방식의 핵심은 세 가지입니다.

첫째, OrderBy와 First(), Last()를 조합하면 정렬 여부와 관계없이 최솟값과 최댓값을 안전하게 구할 수 있습니다.
둘째, Enumerable.Range는 시작 값부터 지정한 개수만큼의 연속된 정수 시퀀스를 손쉽게 생성합니다.
셋째, Except는 두 컬렉션의 차집합을 반환하므로, 전체 범위에서 기존 값을 제거하면 누락된 숫자만 남게 됩니다.

참고로 리스트가 이미 오름차순으로 정렬되어 있다면 myList.First()와 myList.Last()를 바로 사용할 수 있어 성능을 더 개선할 수 있습니다. 또한 중복 값이 있는 경우에도 Except가 집합 연산으로 동작하므로 결과에는 영향을 주지 않습니다.