[C언어]백준 1920번: 수 찾기

https://www.acmicpc.net/problem/1920

1920번: 수 찾기

---

• 문제

---

• 문제풀이

이진탐색트리를 사용하여 시간초과를 만들지 않는것이 핵심이다.

#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;
}

 

---

• 후기

점점 포인터가 많아진다 어렵다