[Gold III] ls - 5015

문제 링크

성능 요약

메모리: 32276 KB, 시간: 224 ms

분류

다이나믹 프로그래밍

문제 설명

현진이는 집에서 취미로 운영 체제를 만들고 있다. 오늘은 디렉토리 안의 파일 리스트를 보여주는 "ls"를 구현해야 할 차례이다. 현진이는 사용자들이 와일드카드(*)를 이용해서 패턴과 일치한 파일 이름을 보여주게 하려고 한다. 와일드 카드는 어떤 문자의 0개 또는 그 이상에 해당한다.

입력

첫째 줄에 패턴 P가 주어진다. P는 1글자~100글자이고, 알파벳 소문자와 '.', '*'로만 이루어져 있다. 둘째 줄에는 디렉토리의 파일 개수 N이 주어진다. (1 ≤ N ≤ 100) 다음 N개의 줄에는 디렉토리에 있는 파일의 이름이 한 줄에 하나씩 주어진다. 파일의 이름은 1글자~100글자이고, 알파벳 소문자와 '.'으로만 이루어져 있다.

출력

패턴 P와 일치하는 파일의 이름을 입력으로 주어진 순서를 따라서 한 줄에 하나씩 출력한다.

---

풀이

아이디어

우선 완전탐색으로 구현한 뒤 dp를 적용한다. 완전 탐색의 경우 코드를 이해하는데 크게 어렵지 않다. 아래는 dp를 적용하지 않은 코드이다.

def is_match(pattern, suffix):
    pos = 0

    # 두 문자열을 비교해서 suffix, pattern 길이보다 pos가 작을때 다음 문자와 비교한다.
    # 문자열이 ? 이거나 같으면 pos를 늘린다.
    while pos < len(suffix) and pos < len(pattern) and \
        (pattern[pos] == '?' or pattern[pos] == suffix[pos]): 
        pos += 1

    # pattern의 끝에 도달한경우
    # 패턴과 suffix의 길이가 정확히 같아야만 둘이 대응한다고 볼 수 있음
    # suffix의 끝에 도달한 경우, pattern의 남은 경우가 모두 *인 경우 대응 가능하므로 아래에서 처리
    if pos == len(pattern):
        return pos == len(suffix)   
    
    # pattern이 *인 경우
    # * 이후의 패턴과 suffix의 접미사를 찾아가면서 재귀호출
    # 만약 이전 조건에 걸리는경우 True를 반환, 그렇지 않으면 남은 재귀호출 완전탐색
    if pattern[pos] == '*':
        for i in range(len(suffix)):
            if pos+i > len(suffix):
                break
            if is_match(pattern[pos+1:], suffix[pos+i:]):
                return True
    
    # 남은 경우는 모두 False
    return False

문제를 조금 바꾸어 와일드 카드 하나를 더 추가해보자. 만약 와일드카드 문자에 ?이 포함된다면 그 문자는 무엇으로든 치환될 수 있다. 예를 들면 he?p 라는 문자열이 들어오면 아래 문자들을 만족한다 heap, help, heup

다음으로 중요한 것은 한 와일드카드 문자가 문자열로 치환될 수 있는 * 문자이다. 아래 문자열은 he*p 일때 만족한다.
heaaaap helloudp, hedup

책에서 재귀로 풀었기 때문에 나도 재귀로 풀었다. (재귀 너무 어려워..)
우선 종료조건 (기저사례)를 뽑아보면 아래와 같다.

• suffix[pos] != pattern[pos] : 서로 대응되지 않으면 당연히 False 이다.

• pattern의 끝에 도달했다 : 패턴에 *이 없는 경우이다. 이 경우에는 pattern과 suffix의 길이가 같아야만 True 이다.

• suffix의 끝에 도달했다 : 패턴은 남았지만 문자열이 끝난경우이다. 이 경우 False이나, 예외 남은 패턴이 모두 *인 경우를 제외한다.

• pattern[pos]가 *인 경우 : *가 몇 글자에 대응할지 모르므로 0글자부터 남은 문자열 길이까지 순회하면서 모든 가능성을 검사한다.

그러나 이를 완전탐색으로 진행하게 될 경우 문자열이 길고 *가 많을 수록 경우의 수가 늘어나므로 시간초과가 발생한다. 예를들면 패턴 ******a와 접미사 aaaaaaaaaaaaaaaab가 그 경우이다.

아이디어 2

집합 자료구조를 이용해 캐시를 구현하였다.

def is_match_cached(pattern, suffix, cache=None):
    print(pattern, suffix, cache)
    if cache is None:
        cache = {}

    if (pattern, suffix) in cache:
        return cache[(pattern, suffix)]

    pos = 0

    while pos < len(suffix) and pos < len(pattern) and \
        (pattern[pos] == '?' or pattern[pos] == suffix[pos]): 
        pos += 1

    if pos == len(pattern):
        result = pos == len(suffix)
    elif pattern[pos] == '*':
        result = False
        for i in range(len(suffix)):
            if pos+i > len(suffix):
                break
            if is_match_cached(pattern[pos+1:], suffix[pos+i:], cache):
                result = True
                break
    else:
        result = False

    cache[(pattern, suffix)] = result
    return result 

캐시는 아래와 같이 작동한다.
입력이 main.c이고 pattern이 *.* 인 경우 캐시에는 이미 계산한 데이터를 저장한다.
set 자료구조에서 탐색은 $O(1)$에 가능하므로 (pattern, suffix) in cache를 수행해도 시간차이가 크지 않으므로 시간초과를 발생시키지 않는다. (파이썬 만세!)

*.* main.c None
.* main.c {}
.* ain.c {('.*', 'main.c'): False}
.* in.c {('.*', 'main.c'): False, ('.*', 'ain.c'): False}
.* n.c {('.*', 'main.c'): False, ('.*', 'ain.c'): False, ('.*', 'in.c'): False}
.* .c {('.*', 'main.c'): False, ('.*', 'ain.c'): False, ('.*', 'in.c'): False, ('.*', 'n.c'): False}
 c {('.*', 'main.c'): False, ('.*', 'ain.c'): False, ('.*', 'in.c'): False, ('.*', 'n.c'): False}
  {('.*', 'main.c'): False, ('.*', 'ain.c'): False, ('.*', 'in.c'): False, ('.*', 'n.c'): False, ('', 'c'): False}
main.c

코드

def is_match_cached(pattern, suffix, cache=None):
    # print(pattern, suffix, cache)
    if cache is None:
        cache = {}

    if (pattern, suffix) in cache:
        return cache[(pattern, suffix)]

    pos = 0

    while pos < len(suffix) and pos < len(pattern) and \
        (pattern[pos] == '?' or pattern[pos] == suffix[pos]): 
        pos += 1

    if pos == len(pattern):
        result = pos == len(suffix)
    elif pattern[pos] == '*':
        result = False
        for i in range(len(suffix)):
            if pos+i > len(suffix):
                break
            if is_match_cached(pattern[pos+1:], suffix[pos+i:], cache):
                result = True
                break
    else:
        result = False

    cache[(pattern, suffix)] = result
    return result 

pattern = input()
for i in range(int(input())):
    if pattern == '*':
        print(input())

    elif(is_match_cached(pattern, k:=input())):
        print(k)
    else:
        continue

여기서 주의할점은 입력패턴이 *으로만 들어온 경우를 예외처리 해준 부분이다.
사실 좀 깔끔하게 만들고 싶었는데,, 음.. 더이상 생각이 안난다.

테스트케이스

아래는 문제를 풀면서 사용했던 테스트케이스이다.

# input
*.*
4
main.c
a.out
readme
yacc

# output
main.c
a.out

# input
*a*a*a
4
aaa
aaaaa
aaaaax
abababa

# output
aaa
aaaaa
abababa

# input

g*iu****y*j*y*h****x***r*m**e**sjz**g*
100
giupvsyljyhmxacprqmgehmsjzg
giuysjyahuxtrjmleosjzkngi
giudayjyhcaxfqhrmekssjzjge
giuwaayjyhlvpxxqrmesjzbgg
gciukwyvjyhxhzdxmvrmyqeyesjzge
gniulfyzjyhxgrfmersjzenegv
giugyjsyhpxntrdmmesjzfg
gyiulyijyphtaxexvrcmesjzgg
guixuayljdyhhjxazbrimjesjzvgn
gmbiudyjmywhyxkarmrlesjzgx
giubzlyjyhdvsxrkrmesjzgs
ghiuvojjyjyyhwwixmrqmpeesjzugm
gqiugcyjkykhcxixrmhevsjzqgi
giuqyxjkyhjxslrymoeoxsjuzgr
giuwyjyhufnxrvrcmesjzpog
giuekgyjdyxhdogbvxzkrmesjzgu
gkiubszyjynhhijxuuxrmogeosjszgd
giuyyoyijdynhyxahnrmzelqsxjzxg
ghiuqyzjyhztsdxcwwrmusetvsjzrwg
gaiuisyrjuynhfxfqrpmsqevsjzag
gimuaywjyhdyxrmesjzpg
gmiuesyxjyhqpxysqramesjzgg
gdiujyhneyjfyhkxqvrmatewsjznegu
giueybjyhxxxprprmeesjzg
gmiucyyjsyqhqxgznrhummesjzlgp
fgfiuibojyejyhfxvvprmkeswsjzzg
giudtyhjlyjhkvuxzqrymeisjzxlg
giujiyjbyohkuxvrjmzseasjzdgr
gsiauuyjyhhhxhrdmzemsjzg
giusdnhybjyhuuxikrcmesjzzgt
giueyijyhonxaframqehsjzngu
gkiueqlcyqjsyhdxyxrmesjzmggk
gjiuoyfjyehxrmjehsjzgs
giuryjyhyxuhrpmqeasjzngh
gaiukjoybjyhhxeromwiesjzjwgf
giuvyjjykhwzxgrmbewqsjzag
giufhsyljayrhirxrmmfejpsjzgng
gkiullyqjjyhxznrmfzebysjzkagu
giubihymjyyhlqxrmjefsjzjgj
giuwyjlyhaxarmekjsjzggx
ghiumatyjjiyhjmxlermjeysjzgt
giuhlpyjjxythlxrjmlevsjzigz
gziuvozbyjryshwxxnermexesjzyg
giuhepyjyphxamrmbeksjzqgl
giuyjqyjyyhexrmhzesjzqgy
gigubzytjyhixcrmfeasjzfgn
dgciujyjayhbfxxkarrmesjzgz
gciudzoyjjymhhpxdrmcesjzsgq
giurnywjyhjswxnqrmtecsjzyfg
giudyjlychcbxoqrvmesjzbug
gjiugvgyzjcyvhimjxdrwmzejrsjzltgh
gxiunyejyghgxkrkmbbecsjztgc
giiulzyljyhkkfxlmrmsesjzsg
giuoyjnythcixlarmiegsjzxg
gsiuynyljydhswxdtrmxiegsjzshg
giusbynjxyhkxyrmaesjzgq
giudeyjyhzfxmarmreawsjzyg
giulysjzyhzvixapzrmquevsjzepg
giugjywjiyhrxbrmeysjzvzg
gbiuquyjhyhxasrmesjzbgw
geiuyjyhsooxhcrzmmteesjzevgy
gkiulqryjybhzbxxlarhmjesjzg
giukchyqjywhvtxprxmxeesjzug
giuhzyjyhehgxfyrhmtexasjzcwgn
giupayjwyjhlxfrmexsjzakg
giuwfztyzjyohzkxlrnmvgesjzsg
gkiumfyzijyahxjfrnmggesjzog
giuhyhjyhbuuxarxmaessjzcg
gxiuhfyljnyafhxunxrmqneksjzmpgw
gdisufyjybhgvxrrrmqesjzbrg
giuayjyxhzqslxyrmemsjyzggq
grsiuxwypjyhgfxdrrmmdesjzgc
giuvmtyjhyshqcxvxrxmvedmsjzdgs
giucniyzjyhktkxllrnmdeasjzsgg
giuqznyjryghnuxdltrmheisjzwgf
gniuggytjyhnxrmbeqsjzg
gmiuroeyjcymhmvxjrfmensjzg
gaiujsyjyuhupxermejesjzg
gwiutybjmyhtnxkermulneksjzwrgv
gniuuzyjiyhsdxvrmwexksjzrg
giuyymjtyrhgsaxrmehsjzygq
giulyyjudythlhbxlmrrcmdesjzccga
giugayejyhyoyxmrrmwejsjzmigk
giusrykjyhtqxqarqmjejsjzljg
geiucgmymjeyhqcvxrzmkeuasjzhgv
gxqiuuyrjyghlbixmbrmdekwsjzgt
giougnyzjlyahxjxalrimesjzgb
gqiuryjcyuhqxmgxvrmmeklsjzg
gpkiukyjyhvvfxermevgsjzygd
gpiutssyjjyhkxqrvmeesjzdgn
gmilujtyjjyhisxprmegasjzqsgj
gciumyjyhonxfrmrneamsjzdg
ggiutyajyhbexucrmplesjzhggq
ghjiuelyjvyuhvbxyxobrmuesjzxgw
goiufyjyuohhxcfrmensjzvg
giuiyjyhffaxrrrmelsjzqgp
gpiuyzjqyhlhtxlrxcmnxesjzacg
gwiukyljysheulxyahrmopessjzxg
gciuuzygjyxhcuxxjrmbesjzpg
giubdpgyjvyhzxgrrmezmsjzgm

# output

giupvsyljyhmxacprqmgehmsjzg
giuysjyahuxtrjmleosjzkngi
giudayjyhcaxfqhrmekssjzjge
giuwaayjyhlvpxxqrmesjzbgg
gciukwyvjyhxhzdxmvrmyqeyesjzge
gniulfyzjyhxgrfmersjzenegv
giugyjsyhpxntrdmmesjzfg
gyiulyijyphtaxexvrcmesjzgg
gmbiudyjmywhyxkarmrlesjzgx
giubzlyjyhdvsxrkrmesjzgs
ghiuvojjyjyyhwwixmrqmpeesjzugm
gqiugcyjkykhcxixrmhevsjzqgi
giuwyjyhufnxrvrcmesjzpog
giuekgyjdyxhdogbvxzkrmesjzgu
ghiuqyzjyhztsdxcwwrmusetvsjzrwg
gaiuisyrjuynhfxfqrpmsqevsjzag
gmiuesyxjyhqpxysqramesjzgg
gdiujyhneyjfyhkxqvrmatewsjznegu
giueybjyhxxxprprmeesjzg
gmiucyyjsyqhqxgznrhummesjzlgp
giudtyhjlyjhkvuxzqrymeisjzxlg
giujiyjbyohkuxvrjmzseasjzdgr
giusdnhybjyhuuxikrcmesjzzgt
giueyijyhonxaframqehsjzngu
gkiueqlcyqjsyhdxyxrmesjzmggk
gjiuoyfjyehxrmjehsjzgs
giuryjyhyxuhrpmqeasjzngh
gaiukjoybjyhhxeromwiesjzjwgf
giuvyjjykhwzxgrmbewqsjzag
giufhsyljayrhirxrmmfejpsjzgng
gkiullyqjjyhxznrmfzebysjzkagu
giubihymjyyhlqxrmjefsjzjgj
giuwyjlyhaxarmekjsjzggx
ghiumatyjjiyhjmxlermjeysjzgt
giuhlpyjjxythlxrjmlevsjzigz
gziuvozbyjryshwxxnermexesjzyg
giuhepyjyphxamrmbeksjzqgl
giuyjqyjyyhexrmhzesjzqgy
gciudzoyjjymhhpxdrmcesjzsgq
giurnywjyhjswxnqrmtecsjzyfg
giudyjlychcbxoqrvmesjzbug
gjiugvgyzjcyvhimjxdrwmzejrsjzltgh
gxiunyejyghgxkrkmbbecsjztgc
giiulzyljyhkkfxlmrmsesjzsg
giuoyjnythcixlarmiegsjzxg
gsiuynyljydhswxdtrmxiegsjzshg
giusbynjxyhkxyrmaesjzgq
giudeyjyhzfxmarmreawsjzyg
giulysjzyhzvixapzrmquevsjzepg
giugjywjiyhrxbrmeysjzvzg
gbiuquyjhyhxasrmesjzbgw
geiuyjyhsooxhcrzmmteesjzevgy
gkiulqryjybhzbxxlarhmjesjzg
giukchyqjywhvtxprxmxeesjzug
giuhzyjyhehgxfyrhmtexasjzcwgn
giupayjwyjhlxfrmexsjzakg
giuwfztyzjyohzkxlrnmvgesjzsg
gkiumfyzijyahxjfrnmggesjzog
giuhyhjyhbuuxarxmaessjzcg
gxiuhfyljnyafhxunxrmqneksjzmpgw
grsiuxwypjyhgfxdrrmmdesjzgc
giuvmtyjhyshqcxvxrxmvedmsjzdgs
giucniyzjyhktkxllrnmdeasjzsgg
giuqznyjryghnuxdltrmheisjzwgf
gniuggytjyhnxrmbeqsjzg
gmiuroeyjcymhmvxjrfmensjzg
gaiujsyjyuhupxermejesjzg
gwiutybjmyhtnxkermulneksjzwrgv
gniuuzyjiyhsdxvrmwexksjzrg
giuyymjtyrhgsaxrmehsjzygq
giulyyjudythlhbxlmrrcmdesjzccga
giugayejyhyoyxmrrmwejsjzmigk
giusrykjyhtqxqarqmjejsjzljg
geiucgmymjeyhqcvxrzmkeuasjzhgv
gxqiuuyrjyghlbixmbrmdekwsjzgt
gqiuryjcyuhqxmgxvrmmeklsjzg
gpkiukyjyhvvfxermevgsjzygd
gpiutssyjjyhkxqrvmeesjzdgn
gciumyjyhonxfrmrneamsjzdg
ggiutyajyhbexucrmplesjzhggq
ghjiuelyjvyuhvbxyxobrmuesjzxgw
goiufyjyuohhxcfrmensjzvg
giuiyjyhffaxrrrmelsjzqgp
gpiuyzjqyhlhtxlrxcmnxesjzacg
gwiukyljysheulxyahrmopessjzxg
gciuuzygjyxhcuxxjrmbesjzpg
giubdpgyjvyhzxgrrmezmsjzgm

# input

**v*****q*ys**vi*k**ij***********sw.***p*w***s*mns*tqzc*j***y*h**a*lr*o.****ct*c*wjq**iy*i**k*m
100
qyvkeqkysviqkijkpddxkdssw.bnpwcsmnstqzcjryhvalro.bectocnwjqniyickum
tvtmqysvimkaijedzusw.bdpdwncsmnsjtqzcjtyhgvafflrqo.dvjctcczwjqoiyijkm
dvetqdyskvitkhijoyjjgsw.kpwwwnsmnstqzcjkyghrlalryo.nactccwjqniygikym
pvrbzqyssvikijqgaiswy.isppwdsmnsdtqzcjbnfyhjazlrbo.zuctscwjqeziyinkm
kvsqysbzvikzijhecwkhsw.sipqwjwhsrmnsotqzcjyuhaylro.dqedctcewjqaiyiukqm
xgvaqmysvwvirkmlyijertzmsw.fpwshmnsbtqzcjmlybhralrro.ctcwjqdiytikm
vjdvrqysfvinkijgisw.mpwcsxrmnsztqzcjgsynhalro.wulctjcowjqkiyihkm
vkquysavikaijsavtmgvsw.escpwzmslmnstqzcijctyihypalro.nkbctcwjqhiyichkm
nvbfuqkysjvimkvijksnskusw.kzpbwjdnsmnsltqzcxjblayhahalro.xprctcwjqiyxiwkxm
uavheqysbbvikoxijbrzqsw.tazpwdwsxmnsutqzcnjzyhvuawlrlo.lzzctmcwjquiyaiikm
vmsyqsysvikkijwxvfhsw.mprwsmnstqzcojdhychjaplryo.aqctuxcswjqgiyickm
gvscukqysvikfzijkbsw.pnpwlsmnsvtqzcajhhiyhaulrpo.kctkdcmwjqkiyhiakjm
vqvqyyslwvikrijkhmdiqzfcsw.rupwlfskmnstqzcjswyshalrqo.zvctxcawjqjiyyiakzm
vwsqystuvikijnzhovxetsw.opwisdmnstqzcjgyvhcaxlrro.iocthctwjqiyiikvm
avqtysviqkijobizxsw.lrpwwysmnsytqzcjnhyjhajlrjo.zmcctcywjqiygikum
viqrysvikqijuukcwzwsw.lpwtzsmnstqzctjyymhalro.qicticxwjqwciyiedkm
oevsrqysvikaijwyysw.lpmwresmnstqzcjhvyohsarlro.tcctcqwjqwviyilkm
cvqhysuvikifijnryhvwsw.hpuwusmnsxtqzcjuyhalroo.mctqcwjqjciymiwkkm
vhoqoyssiviklyijkpifwsw.okpwbdsmmnstqzcnjoeyyhmbaalro.eecctzcmwjqgityvifkm
vuoqeysuvihkijuqjwwsw.epwbnsezmnsntqzcjjyhhepalro.vuctcwjqoyiyiuksm
ovqqysvikyijtzapygcmsw.pwsmnstqzcgjwybhggalrro.mctcwjqsiyizkkm
gvtxaylqhyslcvikmijvurvpusw.lnpiwvsmnsetqzcjqyhoalruo.kctocwjqiiygihekem
zvkwqgysviyklijkeysrdsw.bpswmosqmnstqzccjkpyhgalro.kctchywjqdiyzikm
bwvjqioqyshmvivklijukocoosw.dpjwnsmnstqzcjayhcalro.qphctccwjqcueiyigkjm
wvdxqxyswviskzijclhkzsw.hpghwsfmnsitqzcjdeyhyjajlro.zctcswjqyiygikym
svyaxjqysgkviaknijazhueusw.epwcusmmnsotqzctjxhyhfbajlro.fwctcuwjquiyikkm
yvghqryshvikhijtzilzdcgsw.oppwlpsmnsptqzcjpyhfxalrfo.dctkcowjqfiyxikksm
vcwqysvikbkijcneprlsw.rpgwsmnsmtqzcjwyhhmaflro.ckctcpwjqkiyyimkbm
gvgoqgyssvikijdracblcsw.zgpwnissdmnstqzcjfpyhgaxlro.ucctcowjqliyikm
dgvqdysviykhijkjghvbksw.pwczlsemnsbtqzcdjlyvhiaelro.ermctdcewjqiyyikpm
lvyayqbysdviekcwijicuzrfsw.hypwcscmnstqzcfjfyshealrgo.mctmcwjqvaiysidzkm
kvsvqpysviklijobqeijsw.djpkwyszmnsitqzcnjpynhwalrao.afjctkcwjqiyirkam
zvzmgcqlysmcavikarijcaliflsw.onpwksmmnstqzcjgyhekalroo.ctucwjqiyikm
vhhqsyseqvikijlhsw.gpwisdmnsatqzcjyhcaslrno.qvctlclwjqqiyoirwkm
yvicqysmbvikcijglrisw.zplwlsmnshtqzcjyhpasluro.iwctgcwjqrliyigdkm
avakqyspqvibkgoijnrreqmossw.upwessmnstqzcjxyhgwalrlo.cctgmcwjqxiyiikm
nvrhsntqiysoxvikgijzldzbzesw.vzpwksmnsbtqzcjkmyhyealro.ldctqcwjqghiyaikm
sxvbepiqysviukgijpbzbrmsw.wpvwsxmnsxtqzcrjyhialrfo.ckwctcwjqgiyriokm
vjwjquysmtvikpijxgisw.kprweusmnsqtqzcojdwyzhalro.nthctczwjqfiyeikm
vtvwqysxavikijuwbensw.mbpewezosmnsktqzcwjzsyhaxlrmo.ffctcwjqiyfiqkem
mvcekqysnzvimkijhpktgasw.wfpqwuusmnstqzcjmzyhhkarlrpo.nxctcswjqiygicmkm
vtsqyskviekijsubpoxsw.fvpbwhsmnsmtqzcjiwybhaelro.cgzctcwjqiyrinnkm
vwaaxqysvimeklqijellkrxjsw.upwsqmnstqzcjqycyuhkaxlro.octcwjqiyiksm
vpgqyysfvikijzqmyysw.lpgwcsmmnsctqzcrjfykhmyalro.zjctbcrwjqxiyaikym
zvfhmqywysysvikijwtifsw.npjwnosmnshtqzcjbvyyhoalro.loctqcwjqaiyiakvm
mvmqiysviekhxijvbaosw.bpwosmnstqzcujvylhzgawlro.ctgcwjqiyuitkom
givgdexqgyslovijkoijztjsw.tppwamsxmnsjtqzcjyohxaclro.ouctcewjqxiyivkm
uvlqysjvijkxiijnolewssw.ehspawoisumnsgtqzcjjyehsaflrxo.gpctfcfwjqftiyibkqam
vzjqxyssviokijlesxivsw.pxpwpsumnstqzcjjhfynhoealro.tuctcpwjqeiyickm
jvqtyspkvidkqijthzdvbvsw.ukxpwhsmnshtqzcvjdcyhalro.xctcpwjqhiyifkm
vdeqfysviakijwejcsw.wpawuimsimnswtqzczjkmtyhaelro.opctncwjquiyivkcm
vwqysmvifkijgiipngsw.ayfphwskmnsytqzccjayohuyallrqfo.mctkcwjqliyiwvkem
vhtmqysivikijbinwpnsw.fpmwsomnstqzckjgyxhkqalrzo.kpicthclwjqgliybiyzkm
yvzvqysvimkiijmgpbyosw.pmwjngsrmnsotqzcjfyxhmalro.vctpcwjqrciymitkm
viltqysovvihkeijkinpoctsw.pgxpwwcbismnstqzcjzxythaalro.wctcpwjqpdiyxiakwm
vzfqyszvipkijhjxbsw.nkypiwlsmnsitqjzcjtyzhccalro.wsvfctcwjqiymikbm
qvorohqyshxovijkijuxtphsw.tcopmwxqsmnstqzctjgoythygalreo.gctgcwjqmjiyqikm
yvpnbqmysgvikijvmxhasw.npwuqsmnstqzcfjryxhqoalryo.mgctcwjqiyiivkm
zvyhrqysvikknxijgnmctsw.ypiwhblslmnsstqzcjsyghaglro.ctsfctqcwjqiyuikom
lpvvmsfqyscvikxijawntusw.pwwsmnsatqzcjlyxhnahlrno.gctmcwjqyiyihdkm
iqvaxbzqlyslevikuijguichsw.jndpvwgtnsxmnswtqzcxjoqyhlalrro.fgjectcwjqziybigkgm
vkneqcysmvivklijqixtzmsw.ypwapsamnsotqzcyjnbybhllalryo.plctcwjqiyciyktm
rvvifwzqcysazvikkijywaynsw.clypuwqslmnshtqzcjyhraplrso.lrnctkcwjqgiyixxkpm
rvwxkqysvikijzomxluwysw.gpiwpsnmnsztqzcjyhalro.tqgctvcwjqxiynixkpm
vnsjqysvbvijkijbrbkwhpsw.kdpwmsomnsktqzcnjvyhyyaqlrwo.pbyctdcwjqziyivvkm
covvucqpysbrvikiijlorbwsw.afpwsmnsgtqzcjsydhaqlro.zjfuctcwjqsiyinkm
qwvfcqkysviknuijracsw.dtpdwnksamnsttqzcqjziyhsailrlo.octcwjqmoiyivhktm
jvbztqysmviikijuyglusw.vxpfwilnssmnsrtqzcpjgyphlalro.ycetmcbwjqciygikzm
vzmqlysdvikiijvugufwzcsw.tqplwvulsmnstqzcjjoyhvoalruo.wctfcdwjqmiyilkm
avzqysvvikijjsw.tbpowpispmnsstqzczjsynhkhalro.ctcwjqniyiyekm
qvodqwysvikijfgdaosw.aidpbwtqspmnstqzcjiywhowazlro.dmctncfwjqqiyiqakm
voylmqysjlvidkcijcyhbktsw.ephwubsgmnsdtqzcjxmmyhzalro.vkctcwjqwiyxirkfm
yvrmqfysudvimkbijoduwbssw.mpwsmnsptqzcujryzhalrbo.dctictwjqyiyoirkm
sovbdqysmvikoyijllyyuyrsw.vpwhskmnsrtqzcujxayhlanlrlo.uctcwjqpiyiskzm
vvxqysavikkijhrhviisw.powqasdmnstqzcjgyhealro.nrctucywjqdjiymilkm
ovviffqysvxviskrijmzmxdnhsw.clpdwarsmnsntqzccjixyhoavlrlo.yxbctcwjqriyiekim
esvorqdysvibkxijqtpsw.olpuwpwsmnstqzcpjruyphlalroko.oxctlcwjqiyyialkum
tvfckqfyszvikrijuntfvxsw.pipiworsmnstqzcqjudyshqaulrro.nscctkcwjqttiyibkum
nvnqpqkysgvivkyijnfpgyltsw.xkapuwsvmnsrtqzcjxzyhsatlruo.pyctcrwjqiiyiektm
nvfqkqysivikfcijlvkgqsw.hpwssjsmnsjtqzcxjxyuhfalro.kdctcwjqmiyfiockkm
yvqojqhysvviiklijzpthisw.ppbwgtsjmnstqzcjdyhtalro.qectchwjqtiybirkm
xvqzqysvjvikqijbkkbesw.hvlpywrvstmnsstqzcjayhcalrgo.mnctcwjqpiyeiksm
qvskqyskviakfnijhgeerxsw.mpywpascmnstqzcxjmyhnawlro.diectncwjqaziyrijkm
vgpzqyshvikijyusw.hzpowsmnstqkzcjiuyhaclro.byctcywjqauiyikm
mohvlojqmystvvikijbhedsw.cpwjlnsemnstqzcjbqyhvalrko.octczwjqciyifkm
ivdwjuiqysvimkfijkrncjalsw.whpufwvzsmnstqzcjpyhjazlrxo.ibtctocwjqeriyuiplkm
vlqiysaviukoijrzoqiygsw.inpewdlysimnstqzcjphcyhhalro.wctcwjqiyjimkm
pvqqjysnwvilkaijdgsjsw.epwfsmnsrtqzckjmybhfeaklrgo.qfcctcywjqiyirlknm
cvjtpqlysavimkqijacnrsw.pplwusrmnsatqzcjujyghrmalroo.actcwjqdviywikikkm
qwvnqysjviakvijrrryuftdsw.vpweusmnsgtqzcpjyylhsalrgo.pwctxcwjqiylixkm
csveqsqysmvikijjcrasw.jvpwdswmnsetqzcrjzjxyqhgoaklrno.vbctccjwjqwniyibkm
kvnugqqysavikpijjnnnpsw.fpwwhskmnsbtqzcjcqtyehyaslrto.actgcwjqdtiyyivkam
vmnytqysviwkylijirhqgccxsw.upswgsrmnsttqzcjmyhyamlro.zvuctjwcwjqiyriwkm
vsvqqysvikijxmrinasw.hptwsrqsqmnstqzcjrqyhpaolrno.ykzctclwjqyoiyeihjkm
svsiqyscvikvijfpzzhsw.xxpwrsmmnstqzchjhqyhhqalro.ffhcticwjqmiyirvkm
cvdqqyspzvidkziijbarxsw.ipwqbsmnsntqzcjteyhtmalro.pctacwjqyiyikqm
qvttqysaviikynijmegrunuqbsw.wpvwgwshmnstqzcejuxyhaalrzo.victcwjqniyiekdmz
vwodzqysvixkzmijkleldsw.zdpwcisvmnsrtqzcjuvyhsalrxo.uoctcgwjqliyiszkfm
vjhewqysdvikijlmrnsw.gepqwsjmnsjtqzcxjheyhkaplrpo.ruqvctcswjqiyikqmr
vezbqysdvixkwijzcagqwasw.keppwvspmnsitqzcqjgmyxhalrao.gjctcdwjqyiyfitkm

# output

qyvkeqkysviqkijkpddxkdssw.bnpwcsmnstqzcjryhvalro.bectocnwjqniyickum
tvtmqysvimkaijedzusw.bdpdwncsmnsjtqzcjtyhgvafflrqo.dvjctcczwjqoiyijkm
dvetqdyskvitkhijoyjjgsw.kpwwwnsmnstqzcjkyghrlalryo.nactccwjqniygikym
kvsqysbzvikzijhecwkhsw.sipqwjwhsrmnsotqzcjyuhaylro.dqedctcewjqaiyiukqm
xgvaqmysvwvirkmlyijertzmsw.fpwshmnsbtqzcjmlybhralrro.ctcwjqdiytikm
vjdvrqysfvinkijgisw.mpwcsxrmnsztqzcjgsynhalro.wulctjcowjqkiyihkm
vkquysavikaijsavtmgvsw.escpwzmslmnstqzcijctyihypalro.nkbctcwjqhiyichkm
nvbfuqkysjvimkvijksnskusw.kzpbwjdnsmnsltqzcxjblayhahalro.xprctcwjqiyxiwkxm
uavheqysbbvikoxijbrzqsw.tazpwdwsxmnsutqzcnjzyhvuawlrlo.lzzctmcwjquiyaiikm
vmsyqsysvikkijwxvfhsw.mprwsmnstqzcojdhychjaplryo.aqctuxcswjqgiyickm
gvscukqysvikfzijkbsw.pnpwlsmnsvtqzcajhhiyhaulrpo.kctkdcmwjqkiyhiakjm
vqvqyyslwvikrijkhmdiqzfcsw.rupwlfskmnstqzcjswyshalrqo.zvctxcawjqjiyyiakzm
vwsqystuvikijnzhovxetsw.opwisdmnstqzcjgyvhcaxlrro.iocthctwjqiyiikvm
avqtysviqkijobizxsw.lrpwwysmnsytqzcjnhyjhajlrjo.zmcctcywjqiygikum
viqrysvikqijuukcwzwsw.lpwtzsmnstqzctjyymhalro.qicticxwjqwciyiedkm
oevsrqysvikaijwyysw.lpmwresmnstqzcjhvyohsarlro.tcctcqwjqwviyilkm
cvqhysuvikifijnryhvwsw.hpuwusmnsxtqzcjuyhalroo.mctqcwjqjciymiwkkm
vuoqeysuvihkijuqjwwsw.epwbnsezmnsntqzcjjyhhepalro.vuctcwjqoyiyiuksm
ovqqysvikyijtzapygcmsw.pwsmnstqzcgjwybhggalrro.mctcwjqsiyizkkm
gvtxaylqhyslcvikmijvurvpusw.lnpiwvsmnsetqzcjqyhoalruo.kctocwjqiiygihekem
zvkwqgysviyklijkeysrdsw.bpswmosqmnstqzccjkpyhgalro.kctchywjqdiyzikm
bwvjqioqyshmvivklijukocoosw.dpjwnsmnstqzcjayhcalro.qphctccwjqcueiyigkjm
wvdxqxyswviskzijclhkzsw.hpghwsfmnsitqzcjdeyhyjajlro.zctcswjqyiygikym
svyaxjqysgkviaknijazhueusw.epwcusmmnsotqzctjxhyhfbajlro.fwctcuwjquiyikkm
yvghqryshvikhijtzilzdcgsw.oppwlpsmnsptqzcjpyhfxalrfo.dctkcowjqfiyxikksm
vcwqysvikbkijcneprlsw.rpgwsmnsmtqzcjwyhhmaflro.ckctcpwjqkiyyimkbm
gvgoqgyssvikijdracblcsw.zgpwnissdmnstqzcjfpyhgaxlro.ucctcowjqliyikm
dgvqdysviykhijkjghvbksw.pwczlsemnsbtqzcdjlyvhiaelro.ermctdcewjqiyyikpm
lvyayqbysdviekcwijicuzrfsw.hypwcscmnstqzcfjfyshealrgo.mctmcwjqvaiysidzkm
kvsvqpysviklijobqeijsw.djpkwyszmnsitqzcnjpynhwalrao.afjctkcwjqiyirkam
zvzmgcqlysmcavikarijcaliflsw.onpwksmmnstqzcjgyhekalroo.ctucwjqiyikm
vhhqsyseqvikijlhsw.gpwisdmnsatqzcjyhcaslrno.qvctlclwjqqiyoirwkm
avakqyspqvibkgoijnrreqmossw.upwessmnstqzcjxyhgwalrlo.cctgmcwjqxiyiikm
nvrhsntqiysoxvikgijzldzbzesw.vzpwksmnsbtqzcjkmyhyealro.ldctqcwjqghiyaikm
sxvbepiqysviukgijpbzbrmsw.wpvwsxmnsxtqzcrjyhialrfo.ckwctcwjqgiyriokm
vjwjquysmtvikpijxgisw.kprweusmnsqtqzcojdwyzhalro.nthctczwjqfiyeikm
vtvwqysxavikijuwbensw.mbpewezosmnsktqzcwjzsyhaxlrmo.ffctcwjqiyfiqkem
mvcekqysnzvimkijhpktgasw.wfpqwuusmnstqzcjmzyhhkarlrpo.nxctcswjqiygicmkm
vtsqyskviekijsubpoxsw.fvpbwhsmnsmtqzcjiwybhaelro.cgzctcwjqiyrinnkm
vwaaxqysvimeklqijellkrxjsw.upwsqmnstqzcjqycyuhkaxlro.octcwjqiyiksm
vpgqyysfvikijzqmyysw.lpgwcsmmnsctqzcrjfykhmyalro.zjctbcrwjqxiyaikym
zvfhmqywysysvikijwtifsw.npjwnosmnshtqzcjbvyyhoalro.loctqcwjqaiyiakvm
mvmqiysviekhxijvbaosw.bpwosmnstqzcujvylhzgawlro.ctgcwjqiyuitkom
givgdexqgyslovijkoijztjsw.tppwamsxmnsjtqzcjyohxaclro.ouctcewjqxiyivkm
uvlqysjvijkxiijnolewssw.ehspawoisumnsgtqzcjjyehsaflrxo.gpctfcfwjqftiyibkqam
vzjqxyssviokijlesxivsw.pxpwpsumnstqzcjjhfynhoealro.tuctcpwjqeiyickm
jvqtyspkvidkqijthzdvbvsw.ukxpwhsmnshtqzcvjdcyhalro.xctcpwjqhiyifkm
vdeqfysviakijwejcsw.wpawuimsimnswtqzczjkmtyhaelro.opctncwjquiyivkcm
vwqysmvifkijgiipngsw.ayfphwskmnsytqzccjayohuyallrqfo.mctkcwjqliyiwvkem
vhtmqysivikijbinwpnsw.fpmwsomnstqzckjgyxhkqalrzo.kpicthclwjqgliybiyzkm
yvzvqysvimkiijmgpbyosw.pmwjngsrmnsotqzcjfyxhmalro.vctpcwjqrciymitkm
viltqysovvihkeijkinpoctsw.pgxpwwcbismnstqzcjzxythaalro.wctcpwjqpdiyxiakwm
qvorohqyshxovijkijuxtphsw.tcopmwxqsmnstqzctjgoythygalreo.gctgcwjqmjiyqikm
yvpnbqmysgvikijvmxhasw.npwuqsmnstqzcfjryxhqoalryo.mgctcwjqiyiivkm
zvyhrqysvikknxijgnmctsw.ypiwhblslmnsstqzcjsyghaglro.ctsfctqcwjqiyuikom
lpvvmsfqyscvikxijawntusw.pwwsmnsatqzcjlyxhnahlrno.gctmcwjqyiyihdkm
iqvaxbzqlyslevikuijguichsw.jndpvwgtnsxmnswtqzcxjoqyhlalrro.fgjectcwjqziybigkgm
vkneqcysmvivklijqixtzmsw.ypwapsamnsotqzcyjnbybhllalryo.plctcwjqiyciyktm
rvvifwzqcysazvikkijywaynsw.clypuwqslmnshtqzcjyhraplrso.lrnctkcwjqgiyixxkpm
rvwxkqysvikijzomxluwysw.gpiwpsnmnsztqzcjyhalro.tqgctvcwjqxiynixkpm
vnsjqysvbvijkijbrbkwhpsw.kdpwmsomnsktqzcnjvyhyyaqlrwo.pbyctdcwjqziyivvkm
covvucqpysbrvikiijlorbwsw.afpwsmnsgtqzcjsydhaqlro.zjfuctcwjqsiyinkm
qwvfcqkysviknuijracsw.dtpdwnksamnsttqzcqjziyhsailrlo.octcwjqmoiyivhktm
vzmqlysdvikiijvugufwzcsw.tqplwvulsmnstqzcjjoyhvoalruo.wctfcdwjqmiyilkm
avzqysvvikijjsw.tbpowpispmnsstqzczjsynhkhalro.ctcwjqniyiyekm
qvodqwysvikijfgdaosw.aidpbwtqspmnstqzcjiywhowazlro.dmctncfwjqqiyiqakm
voylmqysjlvidkcijcyhbktsw.ephwubsgmnsdtqzcjxmmyhzalro.vkctcwjqwiyxirkfm
yvrmqfysudvimkbijoduwbssw.mpwsmnsptqzcujryzhalrbo.dctictwjqyiyoirkm
sovbdqysmvikoyijllyyuyrsw.vpwhskmnsrtqzcujxayhlanlrlo.uctcwjqpiyiskzm
vvxqysavikkijhrhviisw.powqasdmnstqzcjgyhealro.nrctucywjqdjiymilkm
ovviffqysvxviskrijmzmxdnhsw.clpdwarsmnsntqzccjixyhoavlrlo.yxbctcwjqriyiekim
esvorqdysvibkxijqtpsw.olpuwpwsmnstqzcpjruyphlalroko.oxctlcwjqiyyialkum
tvfckqfyszvikrijuntfvxsw.pipiworsmnstqzcqjudyshqaulrro.nscctkcwjqttiyibkum
nvnqpqkysgvivkyijnfpgyltsw.xkapuwsvmnsrtqzcjxzyhsatlruo.pyctcrwjqiiyiektm
nvfqkqysivikfcijlvkgqsw.hpwssjsmnsjtqzcxjxyuhfalro.kdctcwjqmiyfiockkm
yvqojqhysvviiklijzpthisw.ppbwgtsjmnstqzcjdyhtalro.qectchwjqtiybirkm
xvqzqysvjvikqijbkkbesw.hvlpywrvstmnsstqzcjayhcalrgo.mnctcwjqpiyeiksm
qvskqyskviakfnijhgeerxsw.mpywpascmnstqzcxjmyhnawlro.diectncwjqaziyrijkm
mohvlojqmystvvikijbhedsw.cpwjlnsemnstqzcjbqyhvalrko.octczwjqciyifkm
ivdwjuiqysvimkfijkrncjalsw.whpufwvzsmnstqzcjpyhjazlrxo.ibtctocwjqeriyuiplkm
vlqiysaviukoijrzoqiygsw.inpewdlysimnstqzcjphcyhhalro.wctcwjqiyjimkm
pvqqjysnwvilkaijdgsjsw.epwfsmnsrtqzckjmybhfeaklrgo.qfcctcywjqiyirlknm
cvjtpqlysavimkqijacnrsw.pplwusrmnsatqzcjujyghrmalroo.actcwjqdviywikikkm
qwvnqysjviakvijrrryuftdsw.vpweusmnsgtqzcpjyylhsalrgo.pwctxcwjqiylixkm
csveqsqysmvikijjcrasw.jvpwdswmnsetqzcrjzjxyqhgoaklrno.vbctccjwjqwniyibkm
kvnugqqysavikpijjnnnpsw.fpwwhskmnsbtqzcjcqtyehyaslrto.actgcwjqdtiyyivkam
vmnytqysviwkylijirhqgccxsw.upswgsrmnsttqzcjmyhyamlro.zvuctjwcwjqiyriwkm
vsvqqysvikijxmrinasw.hptwsrqsqmnstqzcjrqyhpaolrno.ykzctclwjqyoiyeihjkm
svsiqyscvikvijfpzzhsw.xxpwrsmmnstqzchjhqyhhqalro.ffhcticwjqmiyirvkm
cvdqqyspzvidkziijbarxsw.ipwqbsmnsntqzcjteyhtmalro.pctacwjqyiyikqm
vwodzqysvixkzmijkleldsw.zdpwcisvmnsrtqzcjuvyhsalrxo.uoctcgwjqliyiszkfm
vezbqysdvixkwijzcagqwasw.keppwvspmnsitqzcqjgmyxhalrao.gjctcdwjqyiyfitkm

# input

*.c*
4
1074.cpp
1463.c
2295.cpp
2503.cpp

# output

1074.cpp
1463.c
2295.cpp
2503.cpp

# input
*
3
aaaaaaaaaaaaaaaa
bbbbbbsdfsbbb
aaaaaaaaaaaaaaaaaaa

# output
aaaaaaaaaaaaaaaa
bbbbbbsdfsbbb
aaaaaaaaaaaaaaaaaaa

# input
******a
1
aaaaaaaaab

# output
[없음]

---

회고

종만북으로 다이나믹프로그래밍을 공부하면서 나온 문제와 유사한 문제라 풀이하였다. 파이썬으로 옮겨 푸는데 너무 오래 걸렸고, 어떻게 이런 아이디어를 냈을까 궁금하다. 사실 내 코드는 ? 문자 와일드카드까지 포함한 코드이다. 종만북 보고 풀어서 그렇다.

생각의 확장을 해야한다. 이게 골드 3 수준이라는거에 놀랐다 정말 갈길이 너무 멀다.

--추가--
갓 파이썬은 fnmatch 모듈이란게 있음..

import fnmatch
pattern = input()
for i in range(int(input())):
    if fnmatch.fnmatch(k:=input(), pattern):
        print(k)