백준(baekjoon) [C] - 1764번: 듣보잡

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

1764번: 듣보잡

---

~~ 실패 코드 ~~

#include <stdio.h>  // 듣보잡
#include <string.h>

char str[500000][21];
char ans[500000][21];
char check[21];

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

	for (int i = 0; i < n; i++)
	{
		scanf("%s", str[i]);
	}
	
	int cnt = 0, ans_idx = 0;
	for (int i = 0; i < m; i++)
	{
		scanf("%s", check);
		for (int j = 0; j < n; j++)
		{
			if (strcmp(str[j], check) == 0)
			{
				strcpy(ans[ans_idx++], check);
				cnt++;
				break;
			}
		}
	}

	printf("%d\n", cnt);
	for (int i = 0; i < ans_idx; i++)
	{
		printf("%s\n", ans[i]);
	}

	return 0;
}

-- 시간초과로 인한 실패

 

~~ 성공 코드 ~~

#include <stdio.h>  // 듣보잡
#include <stdlib.h>
#include <string.h>

int compare(void* first, void* second)
{
	return strcmp(first, second);
}

typedef struct
{
	char input[21];
}name;

typedef struct
{
	char save[21];
}ans;

name str1[1000001];
ans str2[500001];


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

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

	qsort(str1, n + m, sizeof(str1[0]), compare);

	int idx = 0;
	for (int i = 0; i < n + m; i++)
	{
		if (strcmp(str1[i].input, str1[i + 1].input) == 0)
		{
			strcpy(str2[idx++].save, str1[i++].input);
		}
	}

	printf("%d\n", idx);
	for (int i = 0; i < idx; i++)
	{
		printf("%s\n", str2[i].save);
	}

	return 0;
}

 -- 시간 초과 문제를 어떻게 해결해야 할지 떠오르지 않아서 구글 검색

-- 참고 링크: https://531522szerodesire.tistory.com/68

---

MEMO

 

!! qsort 비교 함수에서 문자열을 사용하는 방법 기억하기 !!