문제

총 N개의 문자열로 이루어진 집합 S가 주어진다.

입력으로 주어지는 M개의 문자열 중에서 집합 S에 포함되어 있는 것이 총 몇 개인지 구하는 프로그램을 작성하시오.

풀이

1. 정렬 후 이진 탐색으로 풀었다.

코드

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#define MAX_SIZE 501

struct String {
    char str[MAX_SIZE];
};

int compareString(const void* a, const void* b) {
    struct String* strA = (struct String*)a;
    struct String* strB = (struct String*)b;
    return strcmp(strA->str, strB->str);
}

int binarySearch(struct String* strings, int n, const char* compare_string) {
    int left = 0;
    int right = n - 1;
    
    while (left <= right) {
        int mid = left + (right - left) / 2;
        int cmp = strcmp(strings[mid].str, compare_string);
        if (cmp == 0) {
            return mid;
        } else if (cmp < 0) {
            left = mid + 1; 
        } else {
            right = mid - 1; 
        }
    }
    
    return -1;
}

int main() {
    int n, m, count = 0;
    scanf("%d %d", &n, &m);

    struct String* strings = (struct String*)malloc(sizeof(struct String) * n);
    if (strings == NULL) {
        perror("Memory allocation failed");
        return 1;
    }

    for (int i = 0; i < n; i++) {
        scanf("%s", strings[i].str);
    }

    qsort(strings, n, sizeof(struct String), compareString);

    char compare_string[MAX_SIZE];
    for (int i = 0; i < m; i++) {
        scanf("%s", compare_string);

        if (binarySearch(strings, n, compare_string) != -1) {
            count++;
        }
    }

    printf("%d\\n", count);

    free(strings);

    return 0;
}