BOJ 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안에 존재하는지 알아내면 된다. 모든 정수의 범위는 -2^31 보다 크거나 같고 2^31보다 작다.
출력
M개의 줄에 답을 출력한다. 존재하면 1을, 존재하지 않으면 0을 출력한다.
재정의와 추상화
문제를 보고 처음 딱 떠오른 algorithm 헤더의 STL 함수가 2개가 있다. 하나는 find(), 하나는 binary_search()이다. 그러면 두 함수를 비교분석해보자.
find 함수
- n개의 element에 대해 O(n)의 시간 복잡도를 가진다.
- 하나 하나 찾는 것이므로, 정렬이 필요가 없다.
- 이는 alrogithm 헤더에 있는 find() 함수에 대한 것이므로, set, map 등에서의 find() 함수는 시간 복잡도가 다르다.
binary_search 함수
- 정렬된 n개의 element에 대해 O(logn)의 시간 복잡도를 가진다.
- 정렬되어 있어야 하므로, O(nlogn)의 시간 복잡도를 가지는 sort() 함수를 먼저 사용해야 한다.
언뜻보면, binary_search가 sort 함수를 함께 써야하기 때문에 더 느리다고 생각할 수 있는데, 실제로 계산해보면 그렇지 않다.
M개의 정수 각각을 배열 A에 있는 N개의 정수에 대해서 탐색해야 하므로, find 함수와 binary_search 함수 + sort 함수를 썼을 때의 시간 복잡도는 아래와 같다.
- find 함수 : M * O(N) = O(MN)
N과 M을 각각 최댓값인 100,000으로 두면, 약 10억(약 10초) - binary_search 함수 : O(NlogN) + M * O(logN) = O((N + M)logN)
N과 M을 각각 최댓값인 100,000으로 두면, 약 20만(약 0.002초)
코드 작성
#include <iostream>
#include <algorithm>
using namespace std;
int main() {
cin.sync_with_stdio(false);
cin.tie(NULL);
cout.tie(NULL);
int n, m;
int a[100000], b[100000];
cin >> n;
for (int i = 0; i < n; i++)
cin >> a[i];
cin >> m;
for (int i = 0; i < m; i++)
cin >> b[i];
sort(a, a + n);
for (int target = 0; target < m; target++)
cout << binary_search(a, a + n, b[target]) << '\n';
return 0;
}
비고
'알고리즘 > 문제풀이' 카테고리의 다른 글
BOJ 1992 - 쿼드트리 문제풀이 (0) | 2020.04.03 |
---|---|
BOJ 6010 - Music Notes 문제풀이 (0) | 2020.04.02 |
BOJ 11055 - 가장 큰 증가 부분 수열 (0) | 2020.04.01 |
BOJ 11048 - 이동하기 문제풀이 (0) | 2020.04.01 |
BOJ 11052 - 카드 구매하기 문제풀이 (0) | 2020.04.01 |
댓글
이 글 공유하기
다른 글
-
BOJ 1992 - 쿼드트리 문제풀이
BOJ 1992 - 쿼드트리 문제풀이
2020.04.03 -
BOJ 6010 - Music Notes 문제풀이
BOJ 6010 - Music Notes 문제풀이
2020.04.02 -
BOJ 11055 - 가장 큰 증가 부분 수열
BOJ 11055 - 가장 큰 증가 부분 수열
2020.04.01 -
BOJ 11048 - 이동하기 문제풀이
BOJ 11048 - 이동하기 문제풀이
2020.04.01