이진탐색을 이용하여 풀면 된다.
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
|
#include<cstdio>
#include<algorithm>
int arr1[500002];
int arr2[500002];
int binary_s(int *ar, int len, int target) {
int first=0;
int last=len-1;
int mid=0;
while(first<=last) {
mid=(first+last)/2;
if(ar[mid]==target) return 1;
else {
if(ar[mid]>target) last=mid-1;
else first=mid+1;
}
}
return 0;
}
int main(void)
{
int n,m;
scanf("%d", &n);
for (int i=0; i<n; i++) scanf("%d", &arr1[i]);
std::sort(arr1, arr1+n);
scanf("%d", &m);
for(int i=0; i<m; i++) scanf("%d", &arr2[i]);
for(int i=0; i<m; i++)
printf("%d ", binary_s(arr1,n,arr2[i]));
return 0;
}
|
cs |
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
|
#include<cstdio>
#include<algorithm>
int arr1[500002];
int arr2[500002];
using namespace std;
int main(void)
{
int n,m,first,last,mid;
scanf("%d", &n);
for (int i=0; i<n; i++) scanf("%d", &arr1[i]);
std::sort(arr1, arr1+n);
scanf("%d", &m);
for(int i=0; i<m; i++) scanf("%d", &arr2[i]);
for(int i=0; i<m; i++) {
if(binary_search(arr1,arr1+n,arr2[i])==1) printf("1 ");
else printf("0 ");
}
return 0;
}
|
cs |
- java
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
|
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.io.IOException;
import java.util.StringTokenizer;
import java.util.Arrays;
public class Main{
public static void main(String[] args) throws IOException{
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
// n 입력받기
int n = Integer.parseInt(br.readLine());
int[] arr = new int[n];
StringTokenizer st = new StringTokenizer(br.readLine(), " ");
for(int i=0; i<n; i++){
arr[i] = Integer.parseInt(st.nextToken());
}
// 정렬
Arrays.sort(arr);
// m 입력받기
int m = Integer.parseInt(br.readLine());
st = new StringTokenizer(br.readLine(), " ");
StringBuilder sb = new StringBuilder();
//
for(int i=0; i<m; i++){
int start=0, end = n;
int target = Integer.parseInt(st.nextToken());
boolean flag = false;
while(start<=end){
int mid = (start+end)/2;
if(arr[mid] == target){
sb.append("1 ");
flag = true;
break;
} else if(arr[mid] < target) {
start = mid+1;
} else
end = mid-1;
}
if(flag == false)
sb.append("0 ");
}
System.out.println(sb);
}
}
|
cs |
'백준 1 > 기타' 카테고리의 다른 글
| [백준 10814] 나이순 정렬 (Java) (0) | 2020.12.17 |
|---|---|
| [백준 14753] Multi Max (C++) (0) | 2020.12.07 |
| [백준 1181] 단어 정렬 (C++/Java) (0) | 2020.12.07 |
| [백준 2230] 수 고르기 (Java) (0) | 2020.12.07 |
| [백준 4458] 첫 글자를 대문자로 (C++) (0) | 2020.12.07 |