[[problem:WILDCARD]]

이 질문은 정답의 소스코드를 포함한 스포일러가 포함되어 있습니다. 이미 푸신분이거나, 너무 간단하서 풀 필요도 없다고 생각하셨던 분들에 한해 봐주세요^;

문제를 풀고나서 (4ms 속도로 품) 문제 구분을 보니, 동적계획법이라고 나와있나요?

그냥 Recursive하게 메모이제이션도 없이 풀었는데, 동적계획법이 나은 이유가 있나요?
아니면, 제가 짠게 동적계획법으로 분류되는건가요?? (그럴리가..)

질문의 요지 : 제 답과 동적계획법의 시간복잡도 차이는 어떻게 되는가?

혹시 모르니, 소스 남겨봅니다. (C)

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

char query[101],files[50][101];
int n;

// 아래 함수는 재귀적으로 호출합니다.
int match(int index, int fs, int ff, int qs, int qf) {
    int i;
    if(qf-qs == 0 && ff - fs == 0)
        return 1;
    if(qf-qs == 0) {
        return 0;
    }
    if(ff-fs == 0 && query[qs] == '*') {
        return match(index,fs,ff,qs+1,qf);
    }
    switch(query[qs]) {
        case '*':
            for(i=fs;i<=ff;i++) {
                if(match(index,i,ff,qs+1,qf)) return 1;
            }
            return 0;
            break;
        case '?':
            if(match(index,fs+1,ff,qs+1,qf)) return 1;
            else return 0;
            break;
        default:
            if(query[qs] == files[index][fs] && match(index, fs+1, ff, qs+1, qf)) return 1;
            else return 0;
    }
}

int main() {
    int i,j,t,n,c,ql,fl,result;
    char sortedIndex[50]; // 나중에 찾은 답을 정렬하기 위한 인덱스 배열
    scanf("%d", &t);
    while(t-- > 0) {
        scanf("%s", query);
        ql=strlen(query);
        scanf("%d", &n);
        result = 0;
        for(i=0;i<n;i++) {
            scanf("%s", files[i]);
            fl=strlen(files[i]);
            if(match(i,0,fl,0,ql)) {
                sortedIndex[result++] = i;
                // 답을 다 찾고 정렬하는 것 보다, insertion sort로 하나씩 추가하며 정렬하는게 더 빠를거라 판단해서 아래는 정렬임(실제로 내용을 바꿔서 정렬하지는 않고, index만 가지고 순서만 바꿈)
                for(j=result-1;j>0;j--) {
                    if(strcmp(files[sortedIndex[j]], files[sortedIndex[j-1]]) < 0) {
                        c = sortedIndex[j];
                        sortedIndex[j] = sortedIndex[j-1];
                        sortedIndex[j-1] = c;
                    } else {
                        break;
                    }
                }
            }
        }
        for(i=0;i<result;i++) {
            printf("%s\n", files[sortedIndex[i]]);
        }
    }
}