문자열 s와 t가 주어졌다고 가정해 봅시다. 이때 t는 모두 대문자로 이루어져 있습니다. 우리는 다음 두 가지 연산만을 사용하여 s를 t로 변환할 수 있는지 확인해야 합니다.
- 일부 소문자를 대문자로 변환하기
- 모든 소문자 제거하기
예를 들어 입력이 s = "fanToM", t = "TOM"이라면 결과는 True입니다. 'o'를 'O'로 바꾼 뒤 나머지 소문자들('f', 'a', 'n')을 모두 제거하면 "TOM"을 얻을 수 있기 때문입니다.
접근 방법: 동적 계획법(DP)
이 문제는 동적 계획법을 활용하면 효율적으로 해결할 수 있습니다. dp[i][j]를 "s의 앞에서 i개 문자를 처리했을 때, t의 앞에서 j개 문자를 만드는 것이 가능한가?"를 나타내는 불리언 값으로 정의합니다.
풀이 과정은 다음과 같습니다.
- n := s의 길이, m := t의 길이로 설정합니다.
- (n+1) × (m+1) 크기의 2차원 배열 dp를 만들고 모든 값을 False로 초기화합니다.
- dp[0][0] := True로 설정합니다. (아무 문자도 처리하지 않은 초기 상태)
- i를 0부터 s의 길이 - 1까지 반복합니다.
- j를 0부터 t의 길이까지 반복합니다.
- dp[i][j]가 True인 경우에만 아래 조건을 검사합니다.
- j < t의 길이이고 s[i]를 대문자로 변환한 값이 t[j]와 같다면 → dp[i+1][j+1] := True (현재 문자를 대문자로 바꿔 t에 포함시키는 경우)
- s[i]가 대문자가 아니라면 → dp[i+1][j] := True (현재 소문자를 제거하는 경우)
- 최종적으로 dp[n][m]을 반환합니다.
구현 예제
다음 구현을 통해 더 자세히 이해해 보겠습니다.
def solve(s,t):
n = len(s)
m = len(t)
dp= [[False for i in range(m+1)] for i in range(n+1)]
dp[0][0] = True
for i in range(len(s)):
for j in range(len(t)+1):
if dp[i][j] == True:
if j < len(t) and (s[i].upper() == t[j]):
dp[i + 1][j + 1] = True
if s[i].isupper()==False:
dp[i + 1][j] = True
return dp[n][m]
s = "fanToM"
t = "TOM"
print(solve(s, t))입력
"fanToM", "TOM"
출력
True
위 코드에서는 각 문자마다 두 가지 선택지를 고려합니다. 해당 문자를 대문자로 변환해 t의 다음 문자와 매칭하거나, 소문자라면 그대로 버리는 것입니다. 최종적으로 dp[n][m]이 True라면 주어진 연산만으로 s를 t로 변환하는 것이 가능하다는 의미입니다.