10816번: 숫자 카드 2

10816번: 숫자 카드 2(BOJ C/C++)

사용 언어: C

문제

숫자 카드는 정수 하나가 적혀져 있는 카드이다. 상근이는 숫자 카드 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개의 수에 대해서, 각 수가 적힌 숫자 카드를 상근이가 몇 개 가지고 있는지를 공백으로 구분해 출력한다.

 

첫 번째 풀이

이분 탐색으로 푸는 것은 알았지만, 통상적인 이분 탐색으로는 중복되는 부분까지는 잡아낼 수 없기 때문에 일단 카운팅 정렬로 풀었다. 카운팅 정렬의 풀이는 메모리가 추가적으로 필요해 공간 복잡도가 높은 대신 시간 복잡도가 O(N)으로 유동적이다(빠를 수도, 느릴 수도).

#include <stdio.h>

int arr[20000001];

int main(void)
{
	int N,M,num;
	scanf("%d",&N);
	for(int i=0;i<N;i++)
	{
		scanf("%d",&num);
		arr[num+10000000]++;
	}
	scanf("%d",&M);
	int data[M];
	for(int i=0;i<M;i++)
		scanf("%d",&data[i]);
	for(int i=0;i<M;i++)
		printf("%d ",arr[data[i]+10000000]);

    return 0;
}

 

두 번째 풀이

이분 탐색으로도 푸는 방법을 알고 싶어서, 다른 분들의 풀이를 참고해봤는데, 이해가 잘 안가지만 이분 탐색의 상한과 하한 값을 빼면 값이 나온다 한다. 원래 이분 탐색은 시간 복잡도가 O(logN)이지만, 여기서는 이분 탐색을 두번 실행하므로 2*O(logN)로 볼 수 있을 것 같다. 백준에서는 첫 풀이가 더 빨랐지만, N이 많이 커진다면 이 풀이가 첫 풀이보다 빨라질 것 같다.

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

int compare(const void *a, const void *b)    // 오름차순 비교 함수 구현
{
    int num1 = *(int *)a;
    int num2 = *(int *)b;

    if(num1 < num2)
        return -1;
    
    if(num1 > num2)
        return 1;
    
    return 0;
}

int lower_binary_search(int arr[], int target, int size) //하한
{
	int mid, start, end;
    start = 0, end = size - 1;
 
    while (end > start)
	{
        mid = (start + end) / 2;
        if (arr[mid] >= target)
            end = mid;
        else start = mid + 1;
    }
    return end;
}

int upper_binary_search(int arr[], int target, int size) //상한
{
	int mid, start, end;
    start = 0, end = size - 1;
 
    while (end > start)
	{
        mid = (start + end) / 2;
        if (arr[mid] > target)
            end = mid;
        else start = mid + 1;
    }
    return end;
}

int main(void)
{
    int lower, upper;
	int N,M;
	scanf("%d",&N);
	int arr[N];
	for(int i=0;i<N;i++)
		scanf("%d",&arr[i]);
	scanf("%d",&M);
	int data[M],res[M];
	for(int i=0;i<M;i++)
	{
		scanf("%d",&data[i]);
		res[i]=0;
	}
	qsort(arr, sizeof(arr)/sizeof(int), sizeof(int),compare);
	for (int i = 0; i < M; i++) 
	{
        lower = lower_binary_search(arr, data[i], N);
        upper = upper_binary_search(arr, data[i], N);
        if (upper == N - 1 && arr[N - 1] == data[i])
            upper++;
        res[i] = upper - lower;
    }
	for (int i=0; i<M; i++)
        printf("%d ",res[i]);

    return 0;
}

 

세 번째 풀이

또 다른 분의 풀이를 보다가 트리로 이 문제를 푸신 본을 봐서 그냥 이렇게 풀 수도 있겠구나~ 생각해서 링크 정도만 올려본다. https://sedangdang.tistory.com/24

 

느낀 점

하나의 문제에서도 이렇게 다양하게 풀 수 있다는 점에서 코딩의 재미를 다시 한번 느낀다. 아자아자 파이팅!