[BOJ][C#] 2776 암기왕

📕 문제

📌 링크

📗 접근 방식

두 리스트를 입력받는다. (list1, list2라고 하자)
이분탐색 시킬 list1을 정렬시킨다. (이분 탐색의 조건)
list2의 요소들을 list1에서 이분탐색한다.

번외 - 연산 효율

나눗셈 보다는 곱하기를 쓰는 것이 더 유리하다고 알고 있었다.
그래서 만약에 x / 2를 해야된다면 x * 0.5를 하는것이 더 좋다.
하지만 비트연산을 이용해
x >> 1을 한다면 x / 2하는 역할을 수행하면서 곱하기보다 더 좋다.
(다음에 블로그 글로 한번 작성해봐야겠다.)

📘 코드

using System.Text;
namespace BOJ_2776
{
    class Program
    {
        static void Main()
        {
            using StreamReader sr = new StreamReader(new BufferedStream(Console.OpenStandardInput()));
            using StreamWriter sw = new StreamWriter(new BufferedStream(Console.OpenStandardOutput()));

            StringBuilder sb = new StringBuilder();

            List<int> list1 = new List<int>();
            List<int> list2 = new List<int>();
            
            int T = int.Parse(sr.ReadLine());
            while (T-- > 0)
            {
                int N = int.Parse(sr.ReadLine());
                list1 = sr.ReadLine().Split().Select(int.Parse).ToList();

                int M = int.Parse(sr.ReadLine());
                list2 = sr.ReadLine().Split().Select(int.Parse).ToList();

                list1.Sort();

                for (int i = 0; i < M; i++)
                {
                    sb.AppendLine(BinarySearch(list2[i], list1));
                }
            }

            sw.Write(sb);
        }

        static string BinarySearch(int target, List<int> list)
        {
            int start = 0;
            int end = list.Count - 1;

            while (start <= end)
            {
                int mid = (start + end) >> 1;

                if (list[mid] < target)
                {
                    start = mid + 1;
                }
                else if(list[mid] > target)
                {
                    end = mid - 1;
                }
                else
                {
                    return "1";
                }
            }

            return "0";
        }
    }
}

📙 오답노트

📒 알고리즘 분류

• 자료 구조
• 정렬
• 이분 탐색
• 해시를 사용한 집합과 맵