[BAEKJOON] 백준 1920 : 수 찾기(C#)

문제 링크

https://www.acmicpc.net/problem/1920

1920번: 수 찾기

 

 

문제

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

 

 

입력

첫째 줄에 자연수 N(1 ≤ N ≤ 100,000)이 주어진다. 다음 줄에는 N개의 정수 A[1], A[2], …, A[N]이 주어진다. 다음 줄에는 M(1 ≤ M ≤ 100,000)이 주어진다. 다음 줄에는 M개의 수들이 주어지는데, 이 수들이 A안에 존재하는지 알아내면 된다. 모든 정수의 범위는 -231 보다 크거나 같고 231보다 작다.

 

 

출력

M개의 줄에 답을 출력한다. 존재하면 1을, 존재하지 않으면 0을 출력한다.

 

 

 

통과한 답안

using System.Text;

namespace _1920
{
    internal class Program
    {
        static void Main(string[] args)
        {
            // 수 찾기
            // N개의 정수 A[1], A[2], ..., A[N]이 주어질 때,
            // 이 안에 X라는 정수가 존재하는지 알아내는 문제

            int N = Convert.ToInt32(Console.ReadLine());
            string[] ss = Console.ReadLine().Split(' ');
            int[] aArr = new int[N];
            
            for (int i = 0; i < aArr.Length; i++)
            {
                aArr[i] = int.Parse(ss[i]);
            }
            Array.Sort(aArr);

            int M = Convert.ToInt32(Console.ReadLine());
            ss = Console.ReadLine().Split(' ');
            StringBuilder sb = new StringBuilder();

            for (int i = 0; i < M; i++)
            {
                int num = int.Parse(ss[i]);
                sb.AppendLine(BinarySearch(aArr, num) ? "1" : "0");
            }

            Console.WriteLine(sb.ToString());
        }

        static bool BinarySearch(int[] arr, int target)
        {
            int left = 0;
            int right = arr.Length - 1;

            while (left <= right)
            {
                int mid = left + (right - left) / 2;
                if (arr[mid] == target)
                {
                    return true;
                }
                else if (arr[mid] < target)
                {
                    left = mid + 1;
                }
                else
                {
                    right = mid - 1;
                }
            }

            return false;
        }
    }
}

 

문제를 이해하기 조금 어려운데 간단히 설명하면

첫째 줄의 입력 값은 Array 1번의 길이를

둘째 줄의 입력 값은 Array 1번의 각 값들을

셋째 줄의 입력 값은 Array 2번의 길이를

넷째 줄의 입력 값을 Array 2번의 각 값들을 주어준다.

이 때, Array 2번의 값들에 대해서

이 값이 Array 1번에 있는 값이라면 1을, 없는 값이라면 0을 return하는 문제.

 

B가 M의 값의 최댓값이 각각 100,000이므로 직접 비교하는 방법은

메모리 초과나 시간 초과로 풀이할 수 없다.

따라서 이분 탐색으로 이를 해결한다.

 

또, 각각 Console.WriteLine을 사용하는 방법도 시간 초과가 날 수 있으므로

Stringbuilder를 사용하여 이를 해결한다.