[백준 C언어] 10815. 숫자 카드

문제

숫자 카드는 정수 하나가 적혀져 있는 카드이다. 상근이는 숫자 카드 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을 공백으로 구분해 출력한다.

 

 

나의 풀이

#include <stdio.h>
#include <stdlib.h>

//대소비교 함수
int cmp(const int* a, const int* b) {
	return *(int*)a > *(int*)b;
}

//이진검색 함수
int search(int arr[], int n, int s) {  //arr : 검색 대상 배열, n : 배열 요소 수, s : 검색값
	int mid, left = 0, right = n - 1;
	while (right >= left) {
		mid = (left + right) / 2;
		if (s == arr[mid]) return 1;
		if (s < arr[mid]) right = mid - 1;
		else left = mid + 1;
	}
	return 0;
}

int main(void) {
	int n, m, s;

	scanf("%d", &n);
	int* arr = (int*)malloc(sizeof(int) * n);
	for (int i = 0; i < n; i++)
		scanf("%d", &arr[i]);

	qsort(arr, n, sizeof(int), cmp);

	scanf("%d", &m);
	for (int i = 0; i < m; i++) {
		scanf("%d", &s);
		printf("%d ", search(arr, n, s));
	}

	free(arr);

	return 0;
}

 

이진 검색으로 풀면 빠르게 해결할 수 있는 문제이다. 

n, m의 최대값이 500,000이기 때문에 순차 검색으로 해결하려 할 경우 

1920번 수 찾기 와 마찬가지로 시간 초과가 나올 수 있다.

(* 이진 검색에 대한 설명이 필요하다면 >>여기 클릭)

 

이진 검색을 사용할 경우 검색 대상 배열이 정렬된 상태여야 한다는 것에 유의하며,

처음 받은 배열을 정렬 후 검색해주면 된다.

 

위 코드의 실행 시간을 아주 조금이라도 더 단축시키고 싶다면...

1. 함수 호출 시간까지 줄이기 위해 search 함수를 밖으로 빼지 않고  main 안에서 기능이 실행되도록 하기

2. malloc으로 메모리를 할당받는 과정을 생략하고 int arr[500000]으로 배열 선언

의 방법이 있을 수 있다. 

 

1번에 대해서는, 기능 함수는 웬만하면 분리해주는 것을 선호하기 때문에 따로 빼준 것이고 

2번은 입력받은 배열이 작을 경우 사용하지 않아도 될 메모리를 잡는 것을 선호하지 않아서 동적할당을 사용했다. 

 

그렇지만...백준 문제의 목적은 프로그래밍을 연습하는 것에 있다고 생각하므로

이 포스팅을 보시는 여러분은 각자의 선호도에 따라서 다양한 방법으로 해보시면 되겠습니다.

 

 

(풀어보기 : https://www.acmicpc.net/problem/10815)