[알고스팟] 와일드카드

문제링크

 Wildcard

• 문제
• 답안 제출
• 통계

문제 정보

• • 문제 ID
  • 시간 제한
  • 메모리 제한
  • 제출 횟수
  • 정답 횟수 (비율)
• • WILDCARD
  • 2000ms
  • 65536kb
  • 6857
  • 2050 (29%)
• • 출제자
  • 출처
  • 분류
• • JongMan
  • 연습문제
  • 보기

문제

와일드카드는 다양한 운영체제에서 파일 이름의 일부만으로 파일 이름을 지정하는 방법이다. 와일드카드 문자열은 일반적인 파일명과 같지만, * 나 ? 와 같은 특수 문자를 포함한다.

와일드카드 문자열을 앞에서 한 글자씩 파일명과 비교해서, 모든 글자가 일치했을 때 해당 와일드카드 문자열이 파일명과 매치된다고 하자. 단, 와일드카드 문자열에 포함된 ? 는 어떤 글자와 비교해도 일치한다고 가정하며, * 는 0 글자 이상의 어떤 문자열에도 일치한다고 본다.

예를 들어 와일드 카드 he?p 는 파일명 help 에도, heap 에도 매치되지만, helpp 에는 매치되지 않는다. 와일드 카드 *p* 는 파일명 help 에도, papa 에도 매치되지만, hello 에는 매치되지 않는다.

와일드카드 문자열과 함께 파일명의 집합이 주어질 때, 그 중 매치되는 파일명들을 찾아내는 프로그램을 작성하시오.

입력

입력의 첫 줄에는 테스트 케이스의 수 C (1 <= C <= 10) 가 주어진다. 각 테스트 케이스의 첫 줄에는 와일드카드 문자열 W 가 주어지며, 그 다음 줄에는 파일명의 수 N (1 <= N <= 50) 이 주어진다. 그 후 N 줄에 하나씩 각 파일명이 주어진다. 파일명은 공백 없이 알파벳 대소문자와 숫자만으로 이루어져 있으며, 와일드카드는 그 외에 * 와 ? 를 가질 수 있다. 모든 문자열의 길이는 1 이상 100 이하이다.

출력

각 테스트 케이스마다 주어진 와일드카드에 매치되는 파일들의 이름을 한 줄에 하나씩 아스키 코드 순서(숫자, 대문자, 소문자 순)대로 출력한다.

예제 입력

2
he?p
3
help
heap
helpp
*p*
3
help
papa
hello

예제 출력

heap
help
help
papa

어떻게 풀까?

가장 까다로운 부분은 바로 '*' 부분입니다.

'*'은 몇 개의 글자도 커버할 수 있기 때문입니다.

몇 개의 글자를 커버할지 모르기 때문에, '*'가 나온다면, '*'가 커버하는 글자를 하나씩 증가시키면서 문제를 생각해봅시다.

예를들면, 

*p*와 help를 비교할 때,

처음에는 *에 글자가 0개 들어간다고 가정하고,

다음에는 h 하나, 그 다음에는 he, 그 다음에는 hel을 넣는 것입니다.

예제에서는 hel에서 매칭이 된다고 나오겠지만, 만약 hel 에서도 답이 나오지 않는다면, *에 help까지 넣어보는 것입니다.

하지만, 이 때 큰 문제가 생깁니다.

만약 문제가 *a*a이고,

aaaaa12345 가 맞는지 매칭을 시도하면 중복해서 계산하는 경우가 생기는 것입니다.

예를 들면, 처음 '*'에는 아무것도 매칭시키지 않고, 2번째 '*'에는 1 까지를 매칭시켰다고 합시다.

다음에 처음 '*'에 a나 aa, aaa를 매칭시켜도 2번째 '*' 부분 1 까지 매칭시켜서 확인할 때 중복으로 계산함을 볼 수 있습니다.

따라서, 이를 위해 '몇 번째 문자열에 몇 번째 와일드카드까지 매칭했다.' 라는 정보를 담고있는 별도의 저장 공간을 만들도록 하겠습니다.

이렇게 하면, '*'가 1에 매칭 됐던 적이 있고, 이 값이 false이기 때문에 어짜피 매칭 해도 안된다는 것을 쉽게 알 수 있습니다.

마지막으로, 답을 출력할 때 문자열을 정렬할 필요가 있는데, 이는 적절한 정렬 알고리즘을 사용합시다.

저는 병합 정렬을 직접 구현했습니다.

코드

//와일드 카드
//알고스팟
//https://algospot.com/judge/problem/read/WILDCARD
 
#pragma once
#include<cstring>
#include<cstdio>
 
int check[100][100];
int len[51];
char str[51][101];
int n, t;
 
int strRes[50];
int temp[50];
int rIdx;
 
void init()
{
    scanf("%s\n", str[0]);
 
    scanf("%d\n", &n);
 
    for (int i = 1; i <= n; i++)
    {
        scanf("%s\n", str[i]);
    }
 
    for (int i = 0; i <= n; i++)
    {
        len[i] = strlen(str[i]);
    }
    rIdx = 0;
}
 
bool match(int sIdx, int sLen, int wLen)
{
    if (sLen == len[sIdx] && wLen == len[0])
    {
        return true;
    }
 
    else if (sLen > len[sIdx] || wLen > len[0]) return false;
 
    if (check[sLen][wLen] != -1) return check[sLen][wLen];
 
    int ret = check[sLen][wLen];
 
    if (str[0][wLen] == '*')
    {
        return ret = match(sIdx, sLen, wLen + 1) || match(sIdx, sLen + 1,wLen);
    }
 
    if (str[0][wLen] != '?' && str[0][wLen] != str[sIdx][sLen])
    {
        check[sLen][wLen] = false;
        return false;
    }
 
    else
    {
        return check[sLen][wLen] = match(sIdx, sLen + 1, wLen + 1);
    }
 
    return false;
}
 
 
void merge(int left, int half, int right)
{
    int l = left, r = half + 1, k = left;
 
    while (l <= half && r <= right)
    {
        if (strcmp(str[strRes[l]], str[strRes[r]]) > 0)
        {
            temp[k++] = strRes[r++];
        }
        else
        {
            temp[k++] = strRes[l++];
        }
    }
 
    while (l <= half) temp[k++] = strRes[l++];
    while (r <= right) temp[k++] = strRes[r++];
 
    for (int i = left; i <= right; i++)
    {
        strRes[i] = temp[i];
    }
}
 
void mergeSort(int left, int right)
{
    if (left < right)
    {
        int half = (left + right) / 2;
        mergeSort(left, half);
        mergeSort(half + 1, right);
 
        merge(left, half, right);
    }
}
 
int main()
{
    scanf("%d\n", &t);
 
    while (t--)
    {
        init();
 
        for (int i = 1; i <= n; i++)
        {
            memset(check, -1, sizeof(check));
            bool res = match(i, 0, 0);
            if (res)
            {
                strRes[rIdx++] = i;
            }
        }
 
        mergeSort(0, rIdx - 1);
 
        for (int i = 0; i < rIdx; i++)
        {
            printf("%s\n", str[strRes[i]]);
        }
    }
 
    return 0;
}