다시푸는 코딩 테스트 준비 일지
문제
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());
}
}
}
코드 결과
