문제 개요
입력 문자열 s와 패턴 문자열 p가 주어졌다고 가정해 봅시다. 이때 s는 원본 문자열이고, p는 비교 대상이 되는 패턴입니다. 우리는 이 문자열 안에서 패턴과 일치하는 부분을 찾아내는 메서드를 정의해야 합니다. 즉, 와일드카드 문자인 물음표('?')와 별표('*')를 지원하는 정규식 스타일의 매칭 기능을 직접 구현하는 것이 목표입니다.
각 와일드카드 문자의 역할은 다음과 같습니다.
- 물음표('?') : 임의의 한 글자와 일치합니다.
- 별표('*') : 0개 이상의 연속된 문자와 일치합니다.
예를 들어, 입력이 s = "aa", p = "a?"라면 결과는 True입니다. 같은 입력 문자열에 대해 패턴이 "?*"인 경우에도 마찬가지로 True가 반환됩니다.
동적 계획법(DP)을 활용한 풀이 전략
이 문제는 동적 계획법을 사용하면 효율적으로 해결할 수 있습니다. 풀이 절차는 다음과 같습니다.
- ss := 문자열 s의 길이, ps := 패턴 p의 길이로 정의합니다.
- (ss+1) × (ps+1) 크기의 DP 테이블(dp)을 만들고 모든 값을 False로 초기화합니다.
- 인덱스 처리를 쉽게 하기 위해 p와 s 앞에 공백 한 칸을 추가합니다.
- i를 1부터 ps까지 순회하며 다음을 수행합니다.
- p[i]가 별표('*')라면 dp[0, i] := dp[0, i - 1]로 설정합니다.
- i를 1부터 ss까지, j를 1부터 ps까지 이중 반복하며 다음을 확인합니다.
- s[i] == p[j]이거나 p[j] == '?'라면, dp[i, j] := dp[i - 1, j - 1]로 갱신합니다.
- 그렇지 않고 p[j] == '*'라면, dp[i, j] := max(dp[i - 1, j], dp[i, j - 1])로 설정합니다.
- 최종적으로 dp[ss, ps]의 값을 반환합니다.
예제 코드 (Python)
아래 구현 예제를 통해 더 자세히 이해해 보겠습니다.
class Solution(object):
def isMatch(self, s, p):
sl = len(s)
pl = len(p)
dp = [[False for i in range(pl+1)] for j in range(sl+1)]
s = " "+s
p = " "+p
dp[0][0]=True
for i in range(1,pl+1):
if p[i] == '*':
dp[0][i] = dp[0][i-1]
for i in range(1,sl+1):
for j in range(1,pl+1):
if s[i] == p[j] or p[j] == '?':
dp[i][j] = dp[i-1][j-1]
elif p[j]=='*':
dp[i][j] = max(dp[i-1][j],dp[i][j-1])
return dp[sl][pl]
ob = Solution()
print(ob.isMatch("aa", "a?"))
print(ob.isMatch("aaaaaa", "a*"))입력
"aa", "a?" "aaaaaa", "a*"
출력
True True
위 코드에서 dp 테이블의 첫 번째 행은 빈 문자열과 패턴의 매칭 여부를 나타냅니다. 패턴이 별표('*')로만 구성된 경우에는 어떤 문자열과도 일치할 수 있으므로, 이전 값(dp[0][i-1])을 그대로 상속받습니다. 이후 이중 반복문을 돌며 각 위치에서 두 문자가 동일하거나 패턴이 물음표('?')인 경우 대각선 위의 값을, 패턴이 별표인 경우 왼쪽 또는 위쪽 값을 참조하여 최종 매칭 결과를 도출합니다.