[알고리즘 / 알고스팟] 문장 찾기 SENTENCE

문제

M개의 문장으로 이뤄진 책이 있다. 각 문장은 길이 1이상 60이하의 문자열이며, 알파벳 문자이거나(대문자 혹은 소문자), 마침표(.), 쉼표(,), 물음표(?) 혹은 빈칸으로 이뤄진다. 문장의 맨 앞이나 뒤에 공백이 오는 경우나, 2개의 빈칸이 나오는 경우는 존재하지 않는다.

독서를 좋아하는 원표는 책을 읽는 도중에 마음에 드는 문장을 메모해 두었는데, 이를 적어놓은 종이에다 연구실 선배인 현환이가 낙서를 해 두었다.
이를 발견하고 원표는 당황했지만, 다행히도 현환이가 적어놓은 낙서와 원표의 낙서는 전연 관계가 없다는것을 알고 안도하였다.
하지만 워낙 낙서를 해논 양이 많았기 때문에, 원표는 자신이 적어놓은 문장과 현환이가 적어놓은 문장을 구분해야한다.
원표는 규칙을 잘 지키고 순서를 중요하는 사람이기 때문에 맘에 드는 문장의 일부분을 적을 때, 아무 부분만 적는게 아니고 문장의 접두어(prefix)의 형태로만 적는다.

책에 적힌 문장과 원표가 쓴 문장과 현환이가 쓴 문장이 주어질 때 원표가 적은 문장을 찾는 프로그램을 작성하라.

입력

입력의 첫번째 줄에는 책에 적힌 문장의 갯수 M과 메모에 적힌 문장의 개수 N이 입력된다. ( 1 <= M <= 1000, 1 <= N <= 10,000 )
그리고 그 다음 M개의 줄에는 문장이 한줄에 하나씩 입력된다. 문장은 위에 명시된 규칙대로 입력된다.
그 다음 N개의 줄에는 원표와 현환이가 적은 문장이 한줄에 한 문장씩 입력된다. 문장의 길이와 형식은 책에 적힌 것과 동일하다.

출력

N개의 문장 중에서 원표가 적은 문장의 갯수를 출력한다.

예를 들어 책에 적힌 문장이
"I am a"
"I am"
라고 하고, "I am" 이라고 할 경우 답은 1이다.

예제 입력

3 4
I will not buy this record, it is scratched.
My hovercraft is full of eels.
Do you want to come back to my place? Bouncy, bouncy.
I will not buy this rec
My helicopter is
Do you want to come back
I will not buy this cat.

예제 출력

2

풀이

난이도에 비해 문제 설명이 장황합니다.
문제는 아주 단순한데요.
우선 책에 적힌 문장의 개수 m과 문장의 내용이 주어지고, 메모에 적힌 문장의 개수 n과 그 문장이  쭉 나오는 것 입니다.
원표가 책에 나온 내용을 적었기 때문에 n개의 문장들 속에는 낙서를 제외하고는 m개 만큼 받은 문장들 속에 딱 들어 맞아야합니다. 딱 맞아떨어지면 전체 카운트에서 하나를 증가시키고 다음 낙서를 처음부터 비교하면 됩니다.
단순하죠? 알고리즘이라기 보다는 구현 문제에 더 가까운 것 같습니다.
어떻게 구현할지 잠시 고민해보시고 아래를 참고해주세요.

답안

#include <stdio.h>
#include <string.h>

int main()
{
	/*FILE* file = freopen("infile.txt", "r", stdin);
	if (file == NULL)
	return 0;
	*/
	char line[1001][61] = {0,};
	int m, n;

	scanf("%d %d", &m, &n);
	for (int i = 0; i <= m; i++)
		gets(line[i]);

	int length = 0, ret = 0;
	for (int i = 0; i < n; i++)
	{
		char str[61] = {0,}; gets(str);
		length = strlen(str);
		for (int j = 0; j <= m; j++)
		{
			if (strncmp(line[j], str, length) == 0)
			{
				ret++;
				break;
			}
		}
	}

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

	return 0;
}