티스토리 뷰
C# collection에 속한 SortedSet에 대해서 살펴보겠습니다.
주요 데이터는 MSDN을 참고하였습니다.
https://docs.microsoft.com/ko-kr/dotnet/api/system.collections.generic.sortedset-1?view=net-5.0
SortedSet 클래스 (System.Collections.Generic)
정렬된 순서대로 유지 관리되는 개체의 컬렉션을 나타냅니다.Represents a collection of objects that is maintained in sorted order.
docs.microsoft.com
https://docs.microsoft.com/ko-kr/dotnet/api/system.collections.generic.hashset-1?view=net-5.0
HashSet 클래스 (System.Collections.Generic)
값 집합을 나타냅니다.Represents a set of values.
docs.microsoft.com
(HashSet도 참고)
Class를 다 뜯어봐서 이렇게 동작한다~~ 라는 글이 아니고 PS할 때, 적당히 사용할 수 있는 정도의 지식만 다룹니다.
C++에서는 Set을 다룰 때, 삽입, 삭제, 검색, 정렬방법 등을 알면 대부분의 문제를 풀 수 있고 구현에 막힘이 없게 이 정도의 매서드만 다룰 예정입니다.
마지막에는 HashSet<T>도 살펴보겠습니다.
1. SortedSet<T>의 특성
C++의 Set과 유사합니다. 연관 컨테이너(assiciative container)로서, 중복 값을 허용하지 않고 어떠한 규칙대로 정렬되어 있는 집합(set)입니다.
기본적인 매서드들을 살펴보겠습니다.
2. SortedSet<T> 구성
2.1) 생성자
처음부터 비어있는 생성자 or 복사할 것이 존재하는 생성자 이렇게 크게 두 가지로 나눌 수 있습니다.
using System;
using System.Collections.Generic;
namespace PS
{
class Solution
{
static void Main(string[] args)
{
Console.WriteLine("-----Set 1-----");
int[] arr = new int[] { 1, 2, 3 };
SortedSet<int> s1 = new SortedSet<int>(arr);
foreach (int item in s1)
Console.WriteLine(item);
Console.WriteLine("-----Set 2-----");
SortedSet<int> s2 = new SortedSet<int>();
foreach (int item in s2)
Console.WriteLine(item);
}
}
}
이렇게 배열을 사용해서 바로 삽입할 수 있습니다. 삽입할 때 시간은 O(nlogn)이고, n은 삽입하는 데이터의 개수입니다.
C++에서는 위 s1처럼 생성과 동시에 삽입하는 게 내부적으로 조금 더 빠르다고 합니다. 그런데 C#은 잘 모르겠습니다. 아마도 동일하지 않을까...라고 생각됩니다!
대부분은 빈 Set을 생성하고 나중에 삽입하는 방법을 많이 사용합니다.
2.2. 매서드
SortedSet에서 주로 사용하는 매서드는 삽입, 삭제가 있습니다. 그리고 집합에 특정 원소가 존재하는지 찾아내는 매서드를 주로 사용합니다.
2.2.1. 삽입
using System;
using System.Collections.Generic;
namespace PS
{
class Solution
{
static void Main(string[] args)
{
SortedSet<int> s = new SortedSet<int>();
Random r = new Random();
for (int i = 0; i < 10; ++i)
{
int value = r.Next() % 20;
if (s.Add(value))
Console.WriteLine($"{value} is added!");
else
Console.WriteLine($"{value} is not added!");
}
Console.WriteLine();
Console.WriteLine("----After adding----");
foreach (int item in s)
Console.WriteLine(item);
}
}
}
삽입하는 매서드는 .Add(object)입니다.
삽입하고자 하는 객체를 인자로 넘겨주면 됩니다. 그리고 삽입에 성공하면 True, 그렇지 않으면 false를 반환합니다.
O(logn)만에 삽입이 됩니다.
2.2.2. 삭제
삭제는 .Remove(object)로 합니다.
using System;
using System.Collections.Generic;
namespace PS
{
class Solution
{
static void Main(string[] args)
{
SortedSet<int> s = new SortedSet<int>(new int[] { 2, 4, 6, 8, 10});
foreach (int item in s)
Console.WriteLine(item);
Console.WriteLine();
Console.WriteLine("---After removing---");
s.Remove(2);
s.Remove(8);
foreach (int item in s)
Console.WriteLine(item);
}
}
}
2.3.3. 포함 여부 확인
또, 삽입, 삭제만큼 중요한 게 포함 여부를 확인하는 것입니다. 'Set에 있으면 넣고 없으면 안 넣는다'는 Add로 구현할 수 있습니다. 대부분, Set에 포함되어있으면 action A, 포함되어 있지 않으면 action B 이렇게 구분하기 위해 사용합니다.
C++에서는 비교할 원소를 인자로 넘겨줍니다. Set.Count(item) == 1이면 Set에 포함되어 있다고 구분합니다. C#에서도 이와 동일하게 Set.Contains(item) == true로 Set에 포함되어 있는지 구분합니다.
using System;
using System.Collections.Generic;
namespace PS
{
class Solution
{
static void Main(string[] args)
{
SortedSet<int> s = new SortedSet<int>(new int[] { 2, 4, 6, 8, 10 });
foreach (int item in s)
Console.WriteLine(item);
Console.WriteLine($"Is 8 in the Set? : {s.Contains(8)}");
Console.WriteLine();
Console.WriteLine("---After removing---");
s.Remove(8);
foreach (int item in s)
Console.WriteLine(item);
Console.WriteLine($"Is 8 in the Set? : {s.Contains(8)}");
}
}
}
그 외 Clear 등.. 이 있지만 자주 사용하지는 않습니다.
2.3. 속성
주로 사용하는 속성은 Count입니다.
C++에서는 .Size()가 있는데 그 Size()에 해당하는 것이 Count입니다.
Count는 현재 Set 내 원소의 개수를 갖고 있습니다.
using System;
using System.Collections.Generic;
namespace PS
{
class Solution
{
static void Main(string[] args)
{
SortedSet<int> s = new SortedSet<int>(new int[] { 2, 4, 6, 8, 10 });
foreach (int item in s)
Console.WriteLine(item);
Console.WriteLine($"Set has : {s.Count} elements");
Console.WriteLine();
Console.WriteLine("---After removing---");
s.Remove(8);
foreach (int item in s)
Console.WriteLine(item);
Console.WriteLine($"Set has : {s.Count} elements");
}
}
}
추가적으로 원소 내의 최소, 최댓값을 갖고 오는 Min, Max 속성도 있습니다.
2.4. 비교자
SortedSet을 쓰는 가장 중요한 이유인 정렬 방법입니다.
C++처럼, Class나 구조체 내부에 bool operator < 처럼 구현하는 방법이 있고, bool operator()처럼 구현하는 방법이 있습니다. 내부적으로 동일한지는 모르겠지만, 'operator <'이 IComparable<T>를 구현하는 것이고, 'operator()'이 IComparer<T>를 구현하는 것입니다.
(참고)
https://docs.microsoft.com/ko-kr/dotnet/api/system.collections.icomparer.compare?view=net-5.0
IComparer.Compare(Object, Object) 메서드 (System.Collections)
두 개체를 비교하여 한 개체가 다른 개체보다 작거나, 같거나 또는 크다는 것을 나타내는 값을 반환합니다.Compares two objects and returns a value indicating whether one is less than, equal to, or greater than the other.
docs.microsoft.com
Class나 구조체가 아닌 자료형에 대해서 operator()(C++), IComparer<T>(C#)을 사용해서 정렬해 보도록 하겠습니다.
using System;
using System.Collections.Generic;
namespace PS
{
class Comp : IComparer<int> // 비교 대상이 int라서 <int>
{
//x : 비교할 첫번째 대상, y : 비교할 두번째 대상
public int Compare(int x, int y)
{
//return 값이 0보다 크면 해당 인스턴스가 정렬상 앞에 존재
// -> return 값이 0보다 크면 x, y랑 자리를 바꿔야 함.
if(x < y)
{
return 1;
// x < y일때 자리를 바꿔야하니까 큰 수가 앞에 존재, 내림차순이 됨.
}
else if(x == y)
{
return 0;
}
else
{
return -1;
}
}
}
class Solution
{
static void Main(string[] args)
{
SortedSet<int> s = new SortedSet<int>(new int[] { 2, 4, 6, 8, 10 },new Comp());
//생성시, 어떤 비교자를 쓸 것인지 인자로 명시
Console.WriteLine("Sorted by Comparer");
foreach (int item in s)
Console.WriteLine(item);
}
}
}
만약, 클래스(구조체) 그 자체에 기본 '정렬 기준' or '정렬 방법'을 정의하고 싶으면 operator <(C++), 즉 IComparable<T>를 구현하면 됩니다.
다음 클래스 Item은 두 개의 속성 (x, y)를 갖습니다. x는 내림차순, y는 오름차순처럼 마음대로 순서를 정의하고 싶을 때는 다음과 같이 합니다.
using System;
using System.Collections.Generic;
namespace PS
{
class Item : IComparable<Item>
{
public Item() { }
public Item(int x_, int y_) { x = x_; y = y_; }
public int x;
public int y;
public int CompareTo(Item other)
{
if (x < other.x)
return 1;
else if (x == other.x)
{
if (y < other.y)
return -1;
else if (y == other.y)
return 0;
else
return 1;
}
else
return -1;
}
}
class Solution
{
static void Main(string[] args)
{
SortedSet<Item> s = new SortedSet<Item>();
var r = new Random();
for (int i = 0; i < 10; ++i)
{
int x = r.Next() % 10;
int y = r.Next() % 10;
if (s.Add(new Item(x, y)))
Console.WriteLine($"({x}, {y}) is added.");
else
Console.WriteLine($"({x}, {y}) is not added.");
}
Console.WriteLine("---Sorted by IComparable---");
foreach (Item item in s)
Console.WriteLine($"({item.x}, {item.y}) ");
}
}
}
위의 비교자는 첫 번째 인자를 내림차순으로, 두 번째 인자는 오름차순으로 정렬한 결과입니다.
특히, 기본 비교자가 Class내부에 구현되어 있지 않습니다. 어떤 class를 SortedSet에 넣고 싶으면 반드시 비교자를 구현해야 합니다. 본인만의 특별한 정렬 순서를 구현하고 싶을 때는 이 CompareTo 함수를 변경해주면 됩니다.
다음은 Class 내부에 비교자를 선언하지 않고 외부에서 어떤 Class에 대한 비교자를 정의한 경우입니다.
using System;
using System.Collections.Generic;
namespace PS
{
class Item
{
public Item() { }
public Item(int x_, int y_) { x = x_; y = y_; }
public int x;
public int y;
}
class Comp : IComparer<Item>
{
public int Compare(Item lhs, Item rhs)
{
if(lhs.x < rhs.x)
{
return 1;
}
else if(lhs.x == rhs.x)
{
if (lhs.y < rhs.y)
{
return -1;
}
else if (lhs.y == rhs.y)
{
return 0;
}
else
{
return 1;
}
}
else
{
return -1;
}
}
}
class Solution
{
static void Main(string[] args)
{
SortedSet<Item> s = new SortedSet<Item>(new Comp());
var r = new Random();
for (int i = 0; i < 10; ++i)
{
int x = r.Next() % 10;
int y = r.Next() % 10;
if (s.Add(new Item(x, y)))
Console.WriteLine($"({x}, {y}) is added.");
else
Console.WriteLine($"({x}, {y}) is not added.");
}
Console.WriteLine("---Sorted by IComparable---");
foreach (Item item in s)
Console.WriteLine($"({item.x}, {item.y}) ");
}
}
}
앞선 실험과 동일한 결과를 보여줍니다.
다시 말해서, IComparable<T>과 IComparer<T> 두 개로 정렬을 마음대로 할 수 있습니다.
3. HashSet<T>
HashSet<T>는 SortedSet<T>에서 정렬 기능을 뺀 Set입니다. Key가 특정 순서로 정렬되어있지 않으면서 Set의 역할을 하는 것입니다.
SortedSet은 IComparable, IComparer를 구현한 Class를 인자로 넘겨줬다면 HashSet은 IEqualityComparer를 구현한 Class를 넘겨주어 Key의 중복을 어떻게 처리할지만 결정하면 됩니다.
기본 자료형은 Default로 구현되어 있기 때문에 HashSet생성시 비교자를 인자로 넘겨주지 않아도 제대로 동작합니다.
특정 Class를 사용해본 예로 마무리 하겠습니다.
using System;
using System.Collections.Generic;
namespace PScs
{
class Point
{
public Point() { }
public Point(int x_, int y_) { x = x_; y = y_; }
public int x { get; set; }
public int y { get; set; }
}
class EqualityComparer : IEqualityComparer<Point>
{
public bool Equals(Point lhs, Point rhs)
{
if (lhs == null && rhs == null)
return true;
else if (lhs == null || rhs == null)
return false;
else if (lhs.x == rhs.x && lhs.y == rhs.y)
return true;
else
return false;
}
public int GetHashCode(Point obj)
{
int hashCode = obj.x ^ obj.y;
return hashCode.GetHashCode();
}
}
class Solution
{
static void Main(string[] args)
{
HashSet<Point> hs = new HashSet<Point>(new EqualityComparer());
hs.Add(new Point(1, 3));
hs.Add(new Point(1, 3));
foreach(var item in hs)
Console.WriteLine($"({item.x}, {item.y})");
}
}
}
2개의 같은 (1, 3) 객체를 삽입했으나 Set에는 1개의 객체만 있는 것을 알 수 있습니다.
삽입에 실패한다고 해서 예외를 던지지는 않습니다.
이것 외로, HashSet은
.UnionWith(HashSet) 합집합
.ExceptWith(HashSet) 차집합
.IntersectWith(HashSet) 교집합
의 기능을 하는 매서드들을 갖고 있습니다.
이렇게 SortedSet<T>에 대해서 알아보았습니다. C++의 Set과 아주 아주 아주 유사하기 때문에 사용처는 동일할 것으로 예상됩니다. C++에서 구현하고 있었던 매서드 등을 모두 C#에서도 구현하고 있었고 다른 부분은 비교자 부분에서
C++은 bool 자료형을 반환하는데 C#은 int형을 반환한다는 점을 예로들 수 있겠습니다.
틀린 부분이나 궁금하신 부분이 있으면 댓글 부탁드립니다^^
'개발 > C#' 카테고리의 다른 글
| [C#/API] API 호출하기 (Json) (0) | 2021.09.02 |
|---|---|
| [C#/Collection] Dictionary<TKey, TValue>, SortedDictionary<TKey, TValue> 분석 (0) | 2021.08.12 |
| [C# / Collection] LinkedList<T> 분석 (0) | 2021.01.03 |
| [C#/JSON] JSON parser 구현 (0) | 2021.01.02 |
| [C#/ XML] XML parser 구현 (0) | 2021.01.01 |