[알고리즘문제] 와일드 카드

알고리즘 문제!! 풀어보기!!

 

Q

 파일 이름을 선택할 때, 와일드 카드(Wild Card) 문자를 사용할 수 있는 기능은 많은 운영체제의 명령어에서 기본적으로 제공하고 있다.

 

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

 

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

 

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

 

 

 

[입력 형식]

 입력 파일의 이름은 INPUT.TXT이다. 첫째 줄에 패턴이 주어진다. 둘째 줄에는 파일명의 개수가 주어지고 세번째줄부터 파일명이 한 줄에 하나씩 입력된다. 패턴과 파일명의 길이는 모두 30을 넘지 않고, 파일명은 최대 100개가 주어진다. 파일명에는 영문 대소문자와 0부터 9까지의 숫자 문자로 구성되어 있다. 파일명의 첫 문자는 숫자 문자가 아니다. 영문 대소문자는 서로 구별된다. 즉, ‘A’와 ‘a’는 다르다.

 

[출력 형식]

 출력 파일의 이름은 OUTPUT.TXT이다. 첫째 줄에 주어진 패턴과 일치하는 파일명의 수를 출력한다. 둘째 줄부터 마지막 줄까지 주어진 패턴과 일치하는 파일명을 한 줄에 하나씩 출력한다. 출력할 파일명은 아무 순서로나 해도 된다.

 

 

 

A

[소스코드]

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

 

char pattern[30] = {'\0', }; // 와일드 카드 값 (즉, 검색할 패턴)
char patternEnd[30] = {'\0', }; // 반대로 저장된 패턴
char data[100][30] = {'\0', }; // 비교할 문자열들
char dataCopy[30] = {'\0', }; // 임시로 복사해둔 문자열, data에서 비교된 문자가 패턴에 적합하면 result에 복사된다. data배열은 비교중에 데이터가 변경되므로, 변경되지 않은 원본을 따로 저장하는 역할을 한다.

char result[100][30] = {'\0', }; // 결과 문자열들

 

int patternCounter = 0; // 패턴의 카운터
int patternEndCounter = 0; // 패턴의 뒤쪽부터의 카운터
int dataEndCounter = 0; // 문자열의 뒤쪽부터의 카운터
int wordCounter = 0; // 파일로 부터 입력받은 파일의 개수
int resultCounter = 0; // 결과 문자열의 개수

 

void InputFile(); // 데이터 입력
void OutputFile(); // 결과 출력
void SetPatternEnd(); // 패턴을 patternEnd에 반대로 저장한다.
bool CompareBasicPattern(int point); // 패턴과 문자열을 비교한다. 문자, ?, * 비교

 

void main()
{
      bool flagEnd = true, onStarSearch = false; // * 가 나타나면 검사 수행 체크

int patternPointer = 0; // 와일드 카드 위치, 문자를 검사할 때, 현재 검사하고 있는 문자의 위치를 저장한다.
int dataPointer=0; //문자열을 비교할때 위치, 문자열의 위치를 저장
int tempPattern = -1;

 

InputFile(); // 파일로부터 데이터 얻어오기

SetPatternEnd();

 

for(int i = 0; i < wordCounter; i++)
{ 

strcpy(dataCopy, data[i]); // 나중에 결과값에 올바른 문자열을 저장하기 위해 dataCopy에 원본 저장
dataEndCounter = strlen(data[i]) - 1; // 문자열의 길이를 가지고, dataEnd의 초기 위치 얻기
patternEndCounter = 0;

 

flagEnd = CompareBasicPattern(i); // 패턴과 문자열 비교

 

while(flagEnd == true)
{

if(pattern[patternPointer] != '*' && pattern[patternPointer] != '?' && pattern[patternPointer] != 0) // patter이 *,? 이 아니라면
{

if(onStarSearch == false) //'*'가 앞에 없을 경우
{
     if(pattern[patternPointer] == data[i][dataPointer]) // 패턴과 문자열의 문자가 같다면
     { 

dataPointer++; // 문자열의 다음 문자로 이동
patternPointer++;// 패턴의 다음 문자로 이동

}
else // 같지 않다면
{

if(data[i][dataPointer] == '\0') // 문자열이 끝났다면 종료
    break;

 

dataPointer++; // 문자열의 다음 포인터로 이동

 

if(tempPattern >= 0)
    patternPointer = tempPattern;
else 
    break;

}

}
else // '*' 가 앞에 있을 경우
{
       while(pattern[patternPointer] != data[i][dataPointer]) // 패턴과 문자열의 데이터가 같지 않다면
       {

      dataPointer++; // 문자열의 데이터만 포인터를 중가시킨다.

 

if(data[i][dataPointer] == '\0') // 문자열이 끝났다면 종료
       break;

 }

 

if(data[i][dataPointer] == '\0') // 문자열이 끝났다면 종료
      break;

 

dataPointer++; // 문자열의 데이터와 패턴의 포인터를 모두 증가시킨다. 
patternPointer++;
onStarSearch = false; // * 탐색 종료

}

}
else if(pattern[patternPointer] == '?') // 패턴에 ?가 있다면
{

if(data[i][dataPointer] == '\0') // 문자열이 끝났다면 종료
     break;
else // 그렇지 않다면 문자열의 데이터와 패턴의 포인터를 모두 증가시킨다.
{
    dataPointer++;
    patternPointer++;
 }

 }
 else if(pattern[patternPointer] == '*') // 패턴에 *가 있다면
 {
        onStarSearch = true; // * 검색모드를 true
        tempPattern = patternPointer;
        patternPointer++;
  }
  else if(pattern[patternPointer] == 0) // 패턴의 비교가 모두 끝났다면, 더이상 비교할 패턴의 문자가 없다면
  {

  if(onStarSearch != true) // * 검색중이 아니었다면, 패턴에 적합한 문자열 처리
  {
       if(data[i][dataPointer] == 0) // 데이터(data)의 문자열의 문자가 모두 소진되었다면
       {

strcpy(result[resultCounter++], dataCopy); // 결과 리스트에 포함
break;

 }
 else // 결과 리스트에 포함시키지 않는다.
      break;

  }
  else // * 검색 중이었다면
  {
      strcpy(result[resultCounter++], dataCopy); // 결과 리스트에 포함
      break;
   }

  }

}

 

// 데이터 초기화
patternPointer = dataPointer = 0;
tempPattern = -1;
flagEnd = true;
onStarSearch = false;

}

 

OutputFile(); // 결과 출력

}

 

 

bool CompareBasicPattern(int point) // 기본적인 패턴 비교
{
    while(patternEnd[patternEndCounter] != '\0') // 패턴(반대로 저장된)에 문자가 남아있다면
    {

if(data[point][dataEndCounter] == patternEnd[patternEndCounter]) // 패턴(반대로 저장된)과 문자열의 문자가 같다면, 뒤에서부터 비교
{

dataEndCounter--;
patternEndCounter++;

}
else if(patternEnd[patternEndCounter] == '?') // 패턴(반대로 저장된)에 ?가 나왔다면 
{

dataEndCounter--;
patternEndCounter++;

}
else
      return false;

}

return true;

}

 

 

void SetPatternEnd() // 패턴을 반대로 저장
{

while(pattern[patternCounter] != '*') // 패턴의 문자중에서 '*'가 나올때까지 (pattern의 뒤에서부터 문자를 읽는다.)
{

patternEnd[patternEndCounter] = pattern[patternCounter]; // pattern의 뒤에서부터 읽은 문자를 patternEnd의 앞쪽부터 쓴다.
pattern[patternCounter] = '\0'; // pattern에서 읽은 데이터는 지운다.

patternCounter--; // 배열의 이동
patternEndCounter++;

}

}

 

 

void InputFile() // 파일로 부터 입력받기
{

FILE *fp; // 파일 포인터 개체
fp = fopen("Input.txt", "r"); // 파일 열기

      fscanf(fp, "%s", pattern); // 패턴 문자열 얻어오기
      fscanf(fp, "%d", &wordCounter); // 입력받은 문자열의 개수 
      patternCounter = strlen(pattern) - 1; // 패턴의 마지막 문자 위치를 patternCounter 에 준다.

 

for(int i = 0; i < wordCounter; i++) // 문자열을 읽어온다.
    fscanf(fp, "%s", data[i]);

 

fclose(fp); // 파일 닫기

}

 

 

void OutputFile()
{

FILE *fp; // 파일 포인터 개체
fp = fopen("Output.txt", "w"); // Output.txt 파일을 쓰기 형식으로 열기

fprintf(fp, "%d\n", resultCounter); // 화면에 출력
printf("%d\n", resultCounter); // 파일에 출력

 

for(int i = 0; i < resultCounter; i++)
{

printf("%s\n", result[i]); // 화면에 출력
fprintf(fp, "%s\n", result[i]); // 파일에 출력

}
printf("결과값은 Output.txt 에 출력되었습니다.\n"); // 결과값 출력

fclose(fp);

}

 

 

 

 

학교다닐 때 짠거라 코드가 좀 초보티가 많이 날 수도 있습니다. ;;;

코드는 C 언어로 작성되었습니다. (Visual Studio 6.0 버전에서 컴파일)

 

 

 

소스 코드 및 실행 파일 받기 (아래 파일 클릭) 

wildcard.zip