(JAVA) 백준 5015번 : ls --- [문자열, DP, 완전탐색]

www.acmicpc.net/problem/5015

5015번: ls

 

안녕하세요.

 

이 문제는 처음에 패턴 보고 정규표현식? 개꿀! 해서 

Pattern과 Matcher를 사용했는데

 

보기좋게 시간초과를 당했었습니다..

 

 

즉, 단순한 정규표현식 문제가 아니라는 뜻인데요.

 

 

도저히 머리가 안굴려져서 

 

고민고민끝에 구글신을 찾았습니다...

 

 

그러다가!

DP와 완탐 재귀를 사용한 방법을 보게 되었는데요..

 

머리 한대 강하게 맞은 것처럼 얼얼했습니다.. 이렇게 생각해서 풀 수 있구나!

 

그래서 해당 블로그 글을 참고하고, 제가 이해하면서 풀게 되었습니다.

 

감사합니다. (stack07142.tistory.com/256)

 

 

 

 

매커니즘

---

패턴 문자열과 비교 문자열 각각 한 문자씩 비교하면 되는데요.

 

각각을 char[] 배열로 만들고,

패턴 문자열의 인덱스를 p, 비교 문자열의 인덱스를 i라고 했을 때

 

p 인덱스의 문자 : 패턴문자열[p]

i 인덱스의 문자 : 비교문자열[i]

 

입니다.

 

즉, 저 두 문자를 비교하는 완탐 해결 방법인데요.

이러한 완탐을 사용하기 위해 int[][] 배열을 하나 만들어서 DP 까지 사용합니다.

 

 

간단하게, 패턴문자열[p] 가 '*' 인 경우를 생각해봅시다.

 

비교하는 함수 이름을 static int patternCheck(int p, int i) 라고 할 때,

 

 

1) 어떤 문자가 0번 포함된 경우

  ->  곧 패턴문자열의 다음 문자로 넘어가면 됩니다. 왜냐? 0번 포함되었기 때문에 *을 건너뛰어야 하니까!

  ->  patternCheck(p + 1, i + 1) 재귀 호출을 통해 얻은 결과가 TRUE인 경우 인덱스 p, 인덱스 i 인 경우에도 TRUE가 됩니다.

 

2) 어떤 문자가 1번 포함된 경우

  ->  패턴문자열의 다음 문자, 비교문자열의 다음 문자로 넘어가면 됩니다.

  ->  patternCheck(p + 1, i + 1) 재귀 호출을 통해 얻은 결과가 TRUE인 경우 인덱스 p, 인덱스 i 인 경우에도 TRUE가 됩니다.

 

3) 어떤 문자가 2번 이상 포함된 경우

  ->  패턴문자열은 냅두고 비교문자열의 다음 문자로 넘어가면 됩니다.

  ->  patternCheck(p, i + 1) 재귀 호출을 통해 얻은 결과가 TRUE인 경우 인덱스 p, 인덱스 i 인 경우에도 TRUE가 됩니다.

 

 

이러한 1),2),3) 과정이 전부 FALSE인 경우에는 패턴과 일치하지 않다는 뜻과 같으므로, 현재 DP배열에 FALSE를 적용시키고 FALSE를 리턴합니다.

반대로, 하나라도 TRUE라면 현재 DP배열에는 TRUE가 적용되고 TRUE를 리턴합니다.

 

 

 

 

다음으로, 패턴문자열[p]가 '*' 외의 문자인 경우를 생각해봅시다.

 

 

패턴문자열[p] == 비교문자열[i] 인 경우에는 patternCheck(p + 1, i + 1) 재귀 호출 후 결과를 현재 DP배열에 적용시키고 리턴합니다.

패턴문자열[p] != 비교문자열[i] 인 경우에는 현재 DP배열에 FALSE를 적용시키고 FALSE를 리턴합니다.

 

 

이렇게 재귀 호출을 통해 DP[0][0] (처음 시작 지점) 의 값을 리턴하게 되고, 해당 리턴 값이 TRUE냐 FALSE냐를 통해 패턴에 부합하는지 아닌지를 알게 됩니다.

 

TRUE인 값만 넣으면 되겠죠!?

 

 

 

아!

이렇게 TRUE / FALSE 외에도 초기 설정값 또한 필요하므로 총 3개의 FLAG 값이 필요합니다.

 

그래서 

 

static final int NONE = -1;

static final int TRUE = 1;

static final int FALSE = 0;

 

NONE, TRUE, FALSE 3개의 FLAG를 활용했습니다.

 

 

또한, 비교문자열 하나하나마다 DP 배열을 초기화해야하므로 Arrays.fill(dp, NONE) 을 호출했었습니다.

 

 

 

더 궁금하신 사항은 댓글 또는 하단 소스코드의 주석을 참고해주세요!

 

감사합니다.

 

 

*** Test Case

1. 

x*y

8

xy

xay

xaby

xabcy

xyz

xayz

xabyz

xabcyz

 

출력

xy

xay

xaby

xabcy

 

2.

*.h

100

aio.h

aliases.h

alloca.h

a.out.h

argp.h

argz.h

ar.h

arpa

asm

assert.h

bits

byteswap.h

clif.h

complex.h

cpio.h

crypt.h

ctype.h

dirent.h

dlfcn.h

elf.h

endian.h

envz.h

err.h

errno.h

error.h

execinfo.h

fcntl.h

features.h

fenv.h

fmtmsg.h

fnmatch.h

fstab.h

fts.h

ftw.h

gconv.h

getopt.h

glob.h

gnu

grp.h

gshadow.h

iconv.h

ifaddrs.h

initreq.h

inttypes.h

langinfo.h

lastlog.h

libgen.h

libintl.h

libio.h

libltdl

limits.h

link.h

linux

locale.h

ltdl.h

malloc.h

math.h

mcheck.h

memory.h

mntent.h

monetary.h

mqueue.h

mtd

net

netash

netatalk

netdb.h

neteconet

netinet

netipx

netiucv

netpacket

netrom

netrose

nfs

nss.h

numpy

obstack.h

openssl

openvpn

paths.h

poll.h

printf.h

protocols

pthread.h

pty.h

pwd.h

rdma

regex.h

regexp.h

resolv.h

rpc

rpcsvc

sched.h

scsi

search.h

semaphore.h

setjmp.h

sgtty.h

shadow.h

 

출력

aio.h

aliases.h

alloca.h

a.out.h

argp.h

argz.h

ar.h

assert.h

byteswap.h

clif.h

complex.h

cpio.h

crypt.h

ctype.h

dirent.h

dlfcn.h

elf.h

endian.h

envz.h

err.h

errno.h

error.h

execinfo.h

fcntl.h

features.h

fenv.h

fmtmsg.h

fnmatch.h

fstab.h

fts.h

ftw.h

gconv.h

getopt.h

glob.h

grp.h

gshadow.h

iconv.h

ifaddrs.h

initreq.h

inttypes.h

langinfo.h

lastlog.h

libgen.h

libintl.h

libio.h

limits.h

link.h

locale.h

ltdl.h

malloc.h

math.h

mcheck.h

memory.h

mntent.h

monetary.h

mqueue.h

netdb.h

nss.h

obstack.h

paths.h

poll.h

printf.h

pthread.h

pty.h

pwd.h

regex.h

regexp.h

resolv.h

sched.h

search.h

semaphore.h

setjmp.h

sgtty.h

shadow.h

 

3.

*

100

aio.h

aliases.h

alloca.h

a.out.h

argp.h

argz.h

ar.h

arpa

asm

assert.h

bits

byteswap.h

clif.h

complex.h

cpio.h

crypt.h

ctype.h

dirent.h

dlfcn.h

elf.h

endian.h

envz.h

err.h

errno.h

error.h

execinfo.h

fcntl.h

features.h

fenv.h

fmtmsg.h

fnmatch.h

fstab.h

fts.h

ftw.h

gconv.h

getopt.h

glob.h

gnu

grp.h

gshadow.h

iconv.h

ifaddrs.h

initreq.h

inttypes.h

langinfo.h

lastlog.h

libgen.h

libintl.h

libio.h

libltdl

limits.h

link.h

linux

locale.h

ltdl.h

malloc.h

math.h

mcheck.h

memory.h

mntent.h

monetary.h

mqueue.h

mtd

net

netash

netatalk

netdb.h

neteconet

netinet

netipx

netiucv

netpacket

netrom

netrose

nfs

nss.h

numpy

obstack.h

openssl

openvpn

paths.h

poll.h

printf.h

protocols

pthread.h

pty.h

pwd.h

rdma

regex.h

regexp.h

resolv.h

rpc

rpcsvc

sched.h

scsi

search.h

semaphore.h

setjmp.h

sgtty.h

shadow.h

 

출력

aio.h

aliases.h

alloca.h

a.out.h

argp.h

argz.h

ar.h

arpa

asm

assert.h

bits

byteswap.h

clif.h

complex.h

cpio.h

crypt.h

ctype.h

dirent.h

dlfcn.h

elf.h

endian.h

envz.h

err.h

errno.h

error.h

execinfo.h

fcntl.h

features.h

fenv.h

fmtmsg.h

fnmatch.h

fstab.h

fts.h

ftw.h

gconv.h

getopt.h

glob.h

gnu

grp.h

gshadow.h

iconv.h

ifaddrs.h

initreq.h

inttypes.h

langinfo.h

lastlog.h

libgen.h

libintl.h

libio.h

libltdl

limits.h

link.h

linux

locale.h

ltdl.h

malloc.h

math.h

mcheck.h

memory.h

mntent.h

monetary.h

mqueue.h

mtd

net

netash

netatalk

netdb.h

neteconet

netinet

netipx

netiucv

netpacket

netrom

netrose

nfs

nss.h

numpy

obstack.h

openssl

openvpn

paths.h

poll.h

printf.h

protocols

pthread.h

pty.h

pwd.h

rdma

regex.h

regexp.h

resolv.h

rpc

rpcsvc

sched.h

scsi

search.h

semaphore.h

setjmp.h

sgtty.h

shadow.h

 

4.

*a*a*a*a*a*a*a*a*a*a*a*a*a*a*a*a*a*a*a*a*a*a*a*a*a*a*a*a*a*a*a*a*a*a*a*a*a*a*a*a*a*a*a*a*a*a*a*a*a*a

4

aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaax

aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa

aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa

xbaacyadaeafagahaiajakalamanaoapaqarasatauavawaxayazabacadaeafagahaiajakalamanaoapaqarasatauavawaxaa

 

출력

aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa

xbaacyadaeafagahaiajakalamanaoapaqarasatauavawaxayazabacadaeafagahaiajakalamanaoapaqarasatauavawaxaa

 

5.

x

1

y

 

출력

 

 

6.

*.c*

4

1074.cpp

1463.c

2295.cpp

2503.cpp

 

출력

1074.cpp

1463.c

2295.cpp

2503.cpp

 

7.

ab*cdf*a

1

abcsdfaa

 

출력

 

 

 

 

출처 : 

https://www.acmicpc.net/board/view/49136

https://www.acmicpc.net/board/view/5522

https://ncpc.idi.ntnu.no/ncpc2011/

https://stack07142.tistory.com/256 [Hello World]

 

 

소스코드

---