Excercism - Sublist 슬라이딩 윈도우

문제요약

두 리스트 간의 관계성을 출력하라

• Equal
• Unequal
• Superlist
• Sublist

https://exercism.org/tracks/csharp/exercises/sublist

Sublist in C# on Exercism

---

난이도

Medium

---

풀이 포인트

• 슬라이딩 윈도우

---

REVIEW

 

슬라이딩 윈도우 개념이 곧바로 떠오르지 않아서 차력으로 풀이했다.

내가 구현한 것도 곧 슬라이딩 윈도우긴 하지만 개념을 잊고 사용했으니 반성.

그리고, 중복되는 코드를 함수로 빼는 습관도 들이자.

우선 되는 게 먼저니까 차력으로 풀어두는 습관이 있는데 이제는 한 단계 나아갈 필요가 있다.

 

Linq사용에 익숙해지고 싶은데, Linq 구절이 여러 개 연속되어 있으면 무슨 뜻인지 이해조차 어렵다.

여튼, 기본적인 슬라이드 윈도우 구현해보기 좋은 문제라 기록해둔다.

---

CODE

// 차력 풀이
using System;
using System.Collections.Generic;

public enum SublistType
{
    Equal,
    Unequal,
    Superlist,
    Sublist
}

public static class Sublist
{
    // 반환 : SublistType
    // 입력 : list 1, list2
    public static SublistType Classify<T>(List<T> list1, List<T> list2)
        where T : IComparable
    {
        // equal , unequal
        if(list1.Count == list2.Count){

            if(list1.Count == 0) return SublistType.Equal;
                
            for(int i =0; i < list1.Count; i++){
                if(!list1[i].Equals( list2[i])) return SublistType.Unequal;
            }
            return SublistType.Equal;
        }
        // sublist, superlist, unequal
        else{
            // superlist, unequal
            if(list1.Count > list2.Count){
                if(list2.Count == 0) return SublistType.Superlist; 
                
                List<int> aIdx = new List<int>();

                for(int i = 0; i < list1.Count ; i++){
                    if(list1[i].Equals( list2[0])) aIdx.Add(i);
                }

                if(aIdx.Count == 0) return SublistType.Unequal;

                bool isFound = true;
                foreach(int a in aIdx){
                   isFound = true;
                    for(int i = 0; i < list2.Count ; i++){
                        if(!list2[i].Equals(list1[a+ i]) ){
                            isFound = false;
                            break;
                        }
                    }  
                    if(isFound){
                        return SublistType.Superlist;
                    }
                }
                
                return SublistType.Unequal;
            }
            // sublist, unequal
            else{

                if(list1.Count == 0) return SublistType.Sublist; 
                // contain 함수로 인덱스 뽑아내는 것 찾기
                List<int> bIdx = new List<int>();
                
                for(int i = 0; i < list2.Count; i++){
                    if(list2[i].Equals(list1[0])) bIdx.Add(i);
                }

                if(bIdx.Count == 0) return SublistType.Unequal;

                bool isFound = true;
                foreach(int b in bIdx){
                    isFound = true;
                    for(int i = 0; i<list1.Count; i++){
                        if(!list1[i].Equals(list2[b + i]))
                        {
                            isFound = false;
                            break;
                        }
                    }
                    if(isFound){
                        return SublistType.Sublist;
                    }
                }
                

                return SublistType.Unequal;
            }
        }
    }
}

// Linq 풀이
using System;
using System.Collections.Generic;
using System.Linq;

public enum SublistType
{
    Equal,
    Unequal,
    Superlist,
    Sublist
}

public static class Sublist
{
    public static SublistType Classify<T>(List<T> list1, List<T> list2)
        where T : IComparable
    {
        if (list1.SequenceEqual(list2))
            return SublistType.Equal;

        if (Contains(list1, list2))
            return SublistType.Sublist;

        if (Contains(list2, list1))
            return SublistType.Superlist;

        return SublistType.Unequal;
    }

    private static bool Contains<T>(List<T> list1, List<T> list2)
    {
        if (list1.Count() == 0)
            return true;
        if (list1.Count() > list2.Count())
            return false;

        return Enumerable.Range(0, list2.Count() - list1.Count() + 1).Any(i => list1.SequenceEqual(list2.Skip(i).Take(list1.Count())));
    }
}