Linq 문제

코드를 짜다가 만난 난제입니다.
다른 분들은 어떻게 하시는 지 문득 궁금해졌습니다.

문제

결과 예시처럼, 정수 시퀀스에서 부분적으로 오름차순으로 연속하는 시퀀스의 첫 정수만 추출하는 LInq 메서드를 작성하시오. 단, 입력값은 정렬됨을 보장하지 않습니다.

IEnumerable<int> Extract(IEnumerable<int> numbers)
{
   // 코드
}

결과 예시

입력: { 1, 2, 5, 6, 8, 9, 10, ... } 
출력: { 1,    5,    8, ... }
5 Likes

입력 값은 정렬되었다고 가정 하나요?

4 Likes

따지지 않습니다.
부분 연속이란 오름차순으로 연속된 것입니다.

4 Likes

연속된 숫자는 고려 하지 않고 단순히

IEnumerable<int> Extract(IEnumerable<int> numbers)
{
            int? prev = null;
            foreach (int number in numbers)
            {
                if (prev == null || number != prev + 1)
                {
                    yield return number;
                }
                prev = number;
            }
}

var result = Extract(
    new List<int> { -1, -1, -2, -1, 0, 1, 2, 4, 5, 6, 8, 8, 9, 10 };
);

[결과]

-1, -1, -2, 4, 8, 8
6 Likes

아쉽습니다.
예제의 입력과 요구하는 출력입니다.

입력: { -1, -1, -2, -1, 0, 1, 2, 4, 5, 6, 8, 8, 9, 10 }
출력: { -2, 4, 8 }
4 Likes

생각보다 코드가 간단하게는 안나오네요.

IEnumerable<int> numbers = [1, 2, 5, 6, 8, 9, 10];
var result = numbers.Extract();
Console.WriteLine($"[{string.Join(", ", result)}]");

IEnumerable<int> numbers2 = [-1, -1, -2, -1, 0, 1, 2, 4, 5, 6, 8, 8, 9, 10];
var result2 = numbers2.Extract();
Console.WriteLine($"[{string.Join(", ", result2)}]");


static class LinqMethodExtension
{
    public static IEnumerable<int> Extract(this IEnumerable<int> @this)
    {
        int? prev = null;
        var distance = 0;
        foreach (var item in @this)
        {
            prev ??= item;

            if (item == prev + distance)
                distance++;
            else
            {
                if (distance > 1)
                    yield return prev.Value;
                prev = item;
                distance = 1;
            }
        }

        if (distance > 1 && prev is not null)
        {
            yield return prev.Value;
        }
    }
}

| 출력

[1, 5, 8]
[-2, 4, 8]
5 Likes

우선 제 스타일로 대충 코드를 짜보면 아래와 같이 나오네요

using System.Linq;

IEnumerable<int> Extract(IEnumerable<int> numbers)
{
    bool findFlag = false;

    for (int i = 0; i < (numbers.Count() - 1); ++i)
    {

        int current = numbers.ElementAt(i);
        int next = numbers.ElementAt(i + 1);

        if ((next - current) is 1)
        {
            if (!findFlag)
            {
                findFlag = true;

                yield return current;
            }
            else
            {
                continue;
            }
        }
        else
        {
            findFlag = false;
        }
    }
}

List<int> target = new() { -1, -1, -2, -1, 0, 1, 2, 4, 5, 6, 8, 8, 9, 10 };
List<int> result = Extract(target).ToList();

result.ForEach(x => Console.WriteLine($"{x} "));

내부 구현을 LINQ로 처리해보고 싶은데…아직 LINQ 실력이 햇병아리인지라 구현이 어렵네요 ㅜㅜ

4 Likes
List<int> list = [-1, -1, -2, -1, 0, 1, 2, 4, 5, 6, 8, 8, 9, 10];
Console.WriteLine(string.Join(", ", Extract(list)));
// output: -2, 4, 8
IEnumerable<int> Extract(IEnumerable<int> numbers)
{
    return numbers.Distinct()
        .Order()
        .Select(x => (Key: x, Result: Enumerable.Repeat(x, 1)))
        .Aggregate((prev, next) => prev.Key + 1 == next.Key ? (next.Key, prev.Result) : (next.Key, prev.Result.Concat(next.Result)))
        .Result;
}

순수 linq만을 이용하려면 이렇게도 가능합니다.

6 Likes

좋은 코드로 참여 감사드립니다.

그런데, 입력값이 IEnumerable인데, 컬렉션으로 가정하신 것 같습니다.
(@URK96 님도 동일합니다)

즉, 보여 주신 코드는, 입력이 아래와 같은 경우에는 값을 반환하지 않습니다.

IEnumerable<int> Numbers()
{
    while(true)
   {
      if (int.TryParse(Console.ReadLine(), out var number))
         yield return number;
   }
}
foreach (var n in Extract(Numbers()))
{
    Console.WriteLine(n); // 실행되지 않음.
}

@dimohy 님의 코드는 그러한 가정이 없기에 정상 동작합니다.

5 Likes

저도 최대한 간단하게 한 번 :grin:

static IEnumerable<int> Extract(IEnumerable<int> numbers)
{
    var prev = numbers.FirstOrDefault();
    var prePrev = prev;
    foreach (var current in numbers.Skip(1))
    {
        if (prePrev + 1 != prev && prev + 1 == current)
            yield return prev;
        (prePrev, prev) = (prev, current);
    }
}

콘솔 입출력

-1
-1
-2
-1
>> -2
0
1
2
4
5
>> 4
6
8
8
9
>> 8
10
8 Likes

앗, 입력으로 yield return이 들어오는 Case는 고려를 못했네요…

단순 호기심으로 참여했던 글인데 예상치 못하게 하나 배워가네요 감사합니다 :slight_smile:

4 Likes

컬렉션과 시퀀스를 분리해서 추상화한 주도 면밀한 마소놈들 때문이죠. ^^

4 Likes
    static void Main(string[] args)
    {
        //List<int> target = [-1, -1, -2, -1, 0, 1, 2, 4, 5, 6, 8, 8, 9, 10];
        List<int> target = [1, 2, 5, 6, 8, 9, 10];
        var result = target.Split(x =>
        {
            if (x == 0)
            {
                if (target[x + 1] == (target[x] + 1))
                    return true;
            }
            else if (target[x - 1] != (target[x] - 1))
                return true;
            return false;
        }).Where(x => x.Count() > 1).Select(x => x.First());

        foreach (var item in result)
            Console.WriteLine(item);
    }

public static class LinqExtention
{
    public static IEnumerable<IEnumerable<TSource>> Split<TSource>(this IEnumerable<TSource> source, Func<int, bool> selector)
    {
        int? start = null;
        for (int i = 0; i < source.Count(); ++i)
        {
            if (selector(i))
            {
                if (start == null)
                {
                    start = i;
                }
                else
                {
                    var temp = start;
                    start = i;
                    yield return source.Skip(temp.Value).SkipLast(source.Count()-i);
                }
            }
        }
        if (start < source.Count())
            yield return source.Skip(start.Value);
    }
}

생각보다 기네요…;;

PS : Extract 라고 만드는 거였네요…;; 난독증이…;;

5 Likes
        IEnumerable<int> Extract(IEnumerable<int> numbers)
        {
            return numbers.Select((x, i) => new { x, i })
                .GroupBy(x => x.x - x.i)
                .Where(i => i.Count() > 1)
                .SelectMany(item => item.Select((x, i) => new { x.x, i })
                    .GroupBy(x => x.x - x.i)
                    .Where(i => i.Count() > 1)
                    .Select(i => i.First().x));
        }

Linq 만 써서 짜봤는데 복잡해서 마음에 안드네요.

5 Likes

참여 감사합니다.
그런데, 동작하지 않습니다.
GroupBy 때문인 것 같습니다.

3 Likes

제 컴퓨터에서는 잘되는 데 이상하네요.

3 Likes

입력을 아래 코드로 대체해보시기 바랍니다.

IEnumerable<int> Numbers()
{
    while(true)
   {
      if (int.TryParse(Console.ReadLine(), out var number))
         yield return number;
   }
}
4 Likes

Linq 메서드는 아니지만, 현재까지 제시된 코드 중, 유일하게 정상 동작하는 코드입니다. 그 짧은 시간에 대단하십니다. :clap:t3: :clap:t3: :clap:t3:
저는 거의 반나절 걸렸습니다.

List<int> list = [-1, -1, -2, -1, 0, 1, 2, 4, 5, 6, 8, 8, 9, 10];

IEnumerable<int> Numbers()
{
   while(true)
   {
      if (int.TryParse(Console.ReadLine(), out var number))
         yield return number;
   }
}

var results = Extract(list);
results = Extract([]);
results = Extract(Numbers());
3 Likes

엇 제꺼도 동작 안하나요??

4 Likes

예. 실패 케이스가 있습니다.
보여주신 입력 데이터가 이 케이스를 숨기고 있는데, 원인은 두 번째 요소의 처리와 관련이 있습니다.

3 Likes