[C#] 백준 1920번 수 찾기

[ 문제 ]

N개의 정수 A[1], A[2], …, A[N]이 주어져 있을 때, 이 안에 X라는 정수가 존재하는지 알아내는 프로그램을 작성하시오.

 

[ 코드 ] 

1. HashSet 사용

using System.Text;

StringBuilder sb = new StringBuilder();
int n = int.Parse(Console.ReadLine());
string[] A = new string[n];
A = Console.ReadLine().Split();
HashSet<string> Aset = new HashSet<string>(A);

int m = int.Parse(Console.ReadLine());
string[] B = new string[m];
B = Console.ReadLine().Split();

foreach(string bVal in B)
{
    bool check = Aset.Contains(bVal);
    sb.AppendLine(check ? "1" : "0");
}
Console.Write(sb);

 

2. Array.BinarySearch 사용

using System.Text;

StringBuilder sb = new StringBuilder();

int n = int.Parse(Console.ReadLine());
string[] A = Console.ReadLine().Split();
Array.Sort(A); 

int m = int.Parse(Console.ReadLine());
string[] B = Console.ReadLine().Split();

foreach (string bVal in B)
{
    bool check = Array.BinarySearch(A, bVal) >= 0;
    sb.AppendLine(check ? "1" : "0");
}

Console.Write(sb);

 

[ 풀이 ]

1. bool check = Aset.Contains(bVal);

> HashSet Aset에서 Contains를 이용해 현재 요소 bVal을 포함하는지 확인한다. 포함되어 있으면 true를 반환하고, 그렇지 않으면 false를 반환한다.

2. bool check = Array.BinarySearch(A, bVal) >= 0;

> 배열 A에서 현재 요소 bVal을 이진 탐색하여 찾는다. Array.BinarySearch 메서드는 요소를 찾으면 해당 인덱스를 반환하고, 찾지 못하면 음수 값을 반환한다. 따라서 포함되어있지 않으면 음수로 false를 반환한다.

 

<HashSet과 Array.BinarySearch 의 차이점>

 

1.데이터의 정렬 여부:

- HashSet: 데이터의 순서가 중요하지 않고, 중복된 요소를 허용하지 않고자 할 때

> 순서가 중요하지 않기 때문에 정렬되지 않은 데이터에 대해서도 효과적이다.

- Array.BinarySearch: 정렬된 데이터에서 특정 값을 빠르게 찾고자 할 때

> 이진 탐색을 사용하므로 데이터가 반드시 정렬되어 있어야 한다.

 

2.검색 속도:

- HashSet: Contains 메서드의 시간 복잡도는 평균적으로 O(1)

> 데이터가 매우 클 경우에도 매우 빠르게 검색 가능하다.

- Array.BinarySearch: 이진 탐색의 시간 복잡도는 O(log n)

> 정렬된 배열에서 빠르게 값을 찾을 수 있지만, 데이터의 크기에 따라 검색 속도 차이O

 

3. 메모리 사용:

- HashSet: 중복된 요소를 허용하지 않으며, 내부적으로 해시 테이블을 사용

> 추가적인 메모리가 필요하다.

- Array.BinarySearch: 정렬된 배열에서 이진 탐색을 수행

> 추가적인 메모리가 필요하지 않다.

 

[ 실행화면 ]

case: 1

---

문제링크: https://www.acmicpc.net/problem/1920

1920번: 수 찾기