코딩테스트 준비 - 수 찾기

다시푸는 코딩 테스트 준비 일지

• 응시 사이트 : BOJ

• 문제 : 1920.수찾기

• 사용언어 : C#

• 난이도 : Easy

• 풀이시간 : 30m Under

• 유형 : 정렬, 이분 탐색, 해쉬

문제

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을 출력한다.

예제 입력 1 복사

5
4 1 5 2 3
5
1 3 7 9 5

예제 출력 1 복사

1
1
0
0
1

문제 풀이 접근

이 문제를 보고 풀이 초기 풀이 방식은 " 이분 탐색 " 만을 생각하고 문제를 풀이했다.
이분 탐색은 탐색 방법 상, 기본 적으로 정렬이 되어있는 배열에서 효과적인 탐색 방법이다.

이분 탐색

현실에서 쉽게 볼 수 있는 곳은 주로 술게임에서 볼 수 있었던 업앤다운 이라는 게임이었다.
1 ~ 50 이라는 사잇수에서 임의의 숫자 13이라고 가정할때, 선택된 숫자가 37 이라고 하면 '업', 45라고 임의의 숫자를 부르면 '다운' 이라고 얘기해서 숫자를 맞추는 게임이다.

제시된 TC는 1 2 3 4 5 라는 정렬된 배열 A 안에 1 3 7 9 5 배열 B의 각 원소가 포함이 되어있느냐 이다.
1을 찾기 위해서는 1 2 3 4 5 에서 1을 left, 5를 right, mid = (left + right)/2 를 하여 중간 값을 설정한다. 그러면 3이 선택되고 찾는 원소인 1은 중간 값 보다 작을 때 right = mid 로 범위를 축소한다.
이렇게 되면 1 2 3 안에서 1 을 찾으면 되고, mid = (left+right)/2 이기 때문에, 2를 중간 값으로 설정하고, 1보다 크기 때문에 right = mid 로 설정한다.
그 이후, 1 2 중에서 mid = (left + right) /2 하면, 1.5 라 인덱스는 1을 찍고, 그래도 1 보다 크기 때문에 right 를 mid, 즉 1로 찍는다.
마지막으로 1,2 중에서 mid = (left + right) /2 하게 되면, (0+1)/2 는 0.5 즉 인덱스 0으로, A[0] =1 로 결국 원하는 수를 찾는다.

횟수는 3번이면 찾는다.
이렇게 찾는 횟수는 선형으로 탐색하는 방식보다 비약적으로 향상된다.

그러나, 이렇게 문제를 풀이하고 제출하게 되면 시간 초과를 만나게 된다.
(문제에서 제공되는 예시 TC는 통과한다.)

그 다음 찾은 방법은 "해쉬맵"을 이용한 방법이다.
해쉬맵은 탐색 시, O(1) 이기 때문에 logN보다는 빠르다.

해쉬 맵

해쉬 맵 사용은 함수를 구현해야하는 이분 탐색보다 편리하다.
초기 주어지는 값들을 모두 hash<int> 로 Add 한 후, B의 원소를 하나씩 해쉬맵 _hs에 Contain 함수로 있는지만 체크하면 쉽게 해결할 수 있다.

작성 코드 (C#) - 이분 탐색 방식 실패 (시간초과)

using System;
using System.Collections;
using System.Collections.Generic;
using System.Xml.Linq;
using static CodingTestProj.Program;
using System.Text;

///*
// * Difficulty : 
// * URL : https://www.acmicpc.net/problem/1920
//  * Time : 
// */

namespace CodingTestProj
{
    internal class Program
    {
        static void Main(string[] args)
        {
            Solution solu = new Solution();
            solu.solve();
        }
    }

    public class Solution
    {
        public int _n;
        public int _m;

        public int[] _arr;
        public int[] _candidate;

        public void solve()
        {
            _n = int.Parse(Console.ReadLine());

            _arr = new int[_n];
            string[] _input = Console.ReadLine().Split(' ');

            for (int i = 0; i < _input.Length; ++i)
                _arr[i] = int.Parse(_input[i]);

            // Array.Sort(_arr);
            // 정렬

            _m = int.Parse(Console.ReadLine());
            _candidate = new int[_m];

            _input = Console.ReadLine().Split(' ');

            for (int i = 0; i < _input.Length; ++i)
                _candidate[i] = int.Parse(_input[i]);
            // Input..

            StringBuilder sb = new StringBuilder();

            for (int i = 0; i < _candidate.Length; ++i)
            {
                if (BinarySearch(_arr, _candidate[i]) != -1)// Finds
                    sb.Append(1);
                else
                    sb.Append(0);

                sb.AppendLine();
            }

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

        public int BinarySearch(int[] _arr, int _searchItem)
        {
            int _ret = -1;
            int _left = 0;
            int _right = _arr.Length - 1;

            while (_left <= _right)
            {
                int mid = (_left + _right) / 2;

                if (_arr[mid] == _searchItem)
                {
                    _ret = 1;
                    break;
                }
                else if (_arr[mid] > _searchItem)
                    _right = mid;
                else if (_arr[mid] < _searchItem)
                    _left = mid + 1;
            }

            return _ret;
        }
    }
}

작성 코드 (C#) - 해쉬맵

using System;
using System.Collections;
using System.Collections.Generic;
using System.Xml.Linq;
using static CodingTestProj.Program;
using System.Text;

///*
// * Difficulty : 
// * URL : https://www.acmicpc.net/problem/1920
//  * Time : 
// */

namespace CodingTestProj
{
    internal class Program
    {
        static void Main(string[] args)
        {
            Solution solu = new Solution();
            solu.solve();
        }
    }

    public class Solution
    {
        public int _n;
        public int _m;

        public int[] _candidate;

        public HashSet<int> _hs;
        public void solve()
        {
            _hs = new HashSet<int>();
            _n = int.Parse(Console.ReadLine());

            string[] _input = Console.ReadLine().Split(' ');

            for(int i = 0;  i < _input.Length; ++i)
                _hs.Add(int.Parse(_input[i]));

            _m = int.Parse(Console.ReadLine());
            _candidate = new int[_m];

            _input = Console.ReadLine().Split(' ');

            for (int i = 0; i < _input.Length; ++i)
                _candidate[i] = int.Parse(_input[i]);
            // Input..

            StringBuilder sb = new StringBuilder();

            for(int i = 0; i < _candidate.Length; ++i)
            {
                if(_hs.Contains(_candidate[i]) == true)
                    sb.Append(1);
                else
                    sb.Append(0);

                sb.AppendLine();
            }

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

코드 결과