SMALL
https://www.acmicpc.net/problem/1920
1920번: 수 찾기
첫째 줄에 자연수 N(1 ≤ N ≤ 100,000)이 주어진다. 다음 줄에는 N개의 정수 A[1], A[2], …, A[N]이 주어진다. 다음 줄에는 M(1 ≤ M ≤ 100,000)이 주어진다. 다음 줄에는 M개의 수들이 주어지는데, 이 수들
www.acmicpc.net
- 문제
- 문제풀이
이진탐색트리를 사용하여 시간초과를 만들지 않는것이 핵심이다.
#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>
#include <stdlib.h>
int main()
{
int a = 0, c = 0, d = 0;
scanf("%d", &a);
int* arr1 = (int*)malloc(sizeof(int) * a);
for (int i = 0; i < a; i++)
{
scanf("%d", &arr1[i]);
}
int b = 0;
scanf("%d", &b);
int* arr2 = (int*)malloc(sizeof(int) * b);
for (int j = 0; j < b; j++)
{
scanf("%d", &arr2[j]);
}
for (int k = 0; k < a; k++)
{
c = 0;
for (int z = 0; z < b; z++)
{
if (arr1[z] == arr2[k])
{
c = 1;
}
}
if (c == 1)
{
printf("1\n");
}
else
{
printf("0\n");
}
}
return 0;
}처음 이런식으로 접근을 했는데 시간초과가 떴었다. 이분탐색을 통해 시간을 단축해야한다.
- 코드 1
#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <search.h>
int ComparePoint(const void* _elem1, const void* _elem2)
{
int* elem1 = (int*)_elem1;
int* elem2 = (int*)_elem2;
if (*elem1 > *elem2)
return 1;
else if (*elem1 < *elem2)
return -1;
else
return 0;
}
int main(void)
{
int n, m;
scanf("%d", &n);
int* arr = (int*)malloc(sizeof(int) * n);
for (int i = 0; i < n; i++)
{
int t;
scanf("%d", &t);
arr[i] = t;
}
scanf("%d", &m);
int* arr2 = (int*)malloc(sizeof(int) * m);
for (int i = 0; i < m; i++)
{
int t;
scanf("%d", &t);
arr2[i] = t;
}
qsort(arr, n, sizeof(int), ComparePoint);
for (int i = 0; i < m; i++)
{
int* find = (int*)bsearch(&arr2[i],
arr,
n,
sizeof(int),
(int(*)(const void*, const void*)) ComparePoint);
if (find != NULL)
{
printf("1\n");
}
else printf("0\n");
}
free(arr);
free(arr2);
return 0;
}
- 후기
점점 포인터가 많아진다 어렵다
LIST
'백준 > C언어' 카테고리의 다른 글
| [C언어]백준 4948번: 베르트랑 공준 (2) | 2023.02.05 |
|---|---|
| [C언어]백준 9020번: 골드바흐의 추측 (0) | 2023.02.05 |
| [C언어]백준 1929번: 소수 구하기 (0) | 2023.02.04 |
| [C언어]백준 1978번: 소수 찾기 (0) | 2023.02.04 |
| [C언어]백준 2960번: 에라토스테네스의 체 (0) | 2023.02.02 |
