2001년 가을학기 문제해결기법 - 문제 6

Wild Card 문자

파일 이름을 선택할 때, wild card 문자를 사용할 수 있는 기능은 많은 운영체제의 명령어에서 기본적으로 제공하고 있다. 이 때, 패턴은 0 혹은 그 이상의 wild card 문자를 포함하고 있고, 이 패턴과 일치하는 파일 이름을 찾게 된다.

자주 사용되는 wild card 문자에는 □*□와 □?□가 있다: □*□는 임의의 0개 이상의 인접한 문자열과 일치하게 되고, □?□는 임의의 문자 하나와 일치하게 된다. 그 외 공백이 아닌 문자는 오직 그 자신과만 일치하게 된다.

예를 들어, 패턴 A?*?X는 파일 이름 ABCX, ABCDX, ABCDEX와 일치되지만, AX나 ABX와는 일치되지 않는다. 패턴 *X*는 X가 어디에나 위치한 파일 이름과 일치되지만, 패턴 ?X*의 경우는 적어도 두 개의 문자를 포함하며 두 번째 위치에 X가 존재하는 파일 이름과 일치한다. 패턴 X*X에서 일치하는 것들은 패턴 X**X에서도 같이 일치하게 된다.

wild card 문자 □*□와 □?□을 포함하는 패턴 하나와 여러 개의 파일명이 주어질 때, 주어진 패턴과 일치하는 파일명을 모두 찾아 출력하는 프로그램을 작성하시오.

프로그램명은 wildcard.c(wildcard.cpp)라고 하고 실행 파일명은 wildcard.exe로 한다. 프로그램의 실행 시간은 5초를 초과할 수 없다.

입력 형식

입력 파일의 이름은 INPUT.TXT이다. 첫째 줄에 패턴이 주어진다. 둘째 줄부터 파일명이 한 줄에 하나씩 입력된다. 마지막 줄에는 달러 문자($)가 입력되어 입력 파일의 끝임을 나타낸다. 패턴과 파일명의 길이는 모두 30을 넘지 않고, 파일명은 최대 100개가 주어진다. 파일명에는 영문 대소문자와 0부터 9까지의 숫자 문자로 구성되어 있다. 파일명의 첫 문자는 숫자 문자가 아니다. 영문 대소문자는 서로 구별된다. 즉, □A'와 □a'는 서로 다르다.

출력 형식

출력 파일의 이름은 OUTPUT.TXT이다. 첫째 줄에 주어진 패턴과 일치하는 파일명의 수를 출력한다. 둘째 줄부터 마지막 줄까지 주어진 패턴과 일치하는 파일명을 한 줄에 하나씩 출력한다. 출력할 파일명이 둘 이상일 때는 반드시 사전식 순서로 정렬하여 출력한다.

입력과 출력의 예

INPUT.TXT

A?*?X

ABCX

ABCDX

ABCDEX

aBCX

AX

ABX

?

OUTPUT.TXT

3

ABCDEX

ABCDX

ABCX