문제
숫자 카드는 정수 하나가 적혀져 있는 카드이다. 상근이는 숫자 카드 N개를 가지고 있다. 정수 M개가 주어졌을 때, 이 수가 적혀있는 숫자 카드를 상근이가 가지고 있는지 아닌지를 구하는 프로그램을 작성하시오.
입력
첫째 줄에 상근이가 가지고 있는 숫자 카드의 개수 N(1 ≤ N ≤ 500,000)이 주어진다. 둘째 줄에는 숫자 카드에 적혀있는 정수가 주어진다. 숫자 카드에 적혀있는 수는 -10,000,000보다 크거나 같고, 10,000,000보다 작거나 같다. 두 숫자 카드에 같은 수가 적혀있는 경우는 없다.
셋째 줄에는 M(1 ≤ M ≤ 500,000)이 주어진다. 넷째 줄에는 상근이가 가지고 있는 숫자 카드인지 아닌지를 구해야 할 M개의 정수가 주어지며, 이 수는 공백으로 구분되어져 있다. 이 수도 -10,000,000보다 크거나 같고, 10,000,000보다 작거나 같다
출력
첫째 줄에 입력으로 주어진 M개의 수에 대해서, 각 수가 적힌 숫자 카드를 상근이가 가지고 있으면 1을, 아니면 0을 공백으로 구분해 출력한다.
1차 코드
#include <algorithm>
#include <iostream>
#include <vector>
using namespace std;
int N;
int M;
int arr1[10000001] = {0, };
int arr2[10000001] = {0, };
vector<int> vec;
int main() {
int a;
cin >> N;
for (int i = 0; i < N; ++i) {
cin >> a;
if(a>=0){
arr1[a] = 1;
}
else{
arr2[-a] = 1;
}
}
cin >> M;
for (int i = 0; i < M; ++i) {
cin >> a;
vec.push_back(a);
}
for(int i=0; i<M; ++i){
if(vec[i] >=0 ){
cout << arr1[vec[i]] << ' ';
}
else{
cout << arr2[-vec[i]] << ' ';
}
}
return 0;
}단순히 이중 반복문으로 작성할 시 시간 복잡도는 .O(MN)이 된다. 이때, M과 N의 최대 크기는 둘다 5*10^6이므로 시간 초과가 발생한다.
이를 해결하기 위해 먼저 떠오른 방법이 N개의 숫자를 키값으로 이용해서 사전 형식처럼 만드는 방법이었다.
다만 주의할 점은 음수일 경우도 있기에 배열을 두개 만들어 하나는 양수, 다른 하나는 음수를 담는 방식으로 해줬다.
이 방법을 이용해서 짠 것이 위의 코드인데 시간 초과를 해결할 수 있어 통과가 되간 한다.
하지만 이 방법은 메모리를 너무 잡아먹는다. 그래서 다음으로 생각한 것이 이분 탐색이다.
2차 코드
#include <algorithm>
#include <iostream>
#include <vector>
using namespace std;
int N;
int M;
int arr1[500001];
int arr2[500001];
int ans[500001] = {0, };
int main() {
cin >> N;
for(int i=0; i<N; ++i){
cin >> arr1[i];
}
cin >> M;
for(int i=0; i<M; ++i){
cin >> arr2[i];
}
sort(arr1, arr1+N); // 오름차순으로 정렬
for(int i=0; i<M; ++i){
int right = N-1;
int left = 0;
while(left<=right){
int mid = (left+right) / 2;
if(arr1[mid] == arr2[i]){
ans[i] = 1;
break;
}
else if(arr1[mid] < arr2[i]){
left = mid+1;
}
else{
right = mid-1;
}
}
}
for(int i=0; i<M; ++i){
cout << ans[i] << ' ';
}
return 0;
}.이분 탐색을 이용한 코드이다.
이분탐색을 이용하기 위해서 먼저 배열을 정렬해야하기 때문에 arr1을 오름차순으로 정렬해 주었고 만약 arr1[mid] 보다 arr2[i]가 크면 left = mid + 1로, 작으면 right = mid - 1로 바꿔주며 탐색을 진행 시켰다.
