소문자로만 이루어진 두 문자열 S와 T가 주어졌을 때, 두 문자열에서 공통으로 만들 수 있는 가장 긴 아나그램(anagram) 부분 수열의 길이를 찾아야 합니다. 여기서 아나그램 부분 수열이란, 문자의 순서를 재배열했을 때 서로 동일해질 수 있는 부분 수열을 의미합니다.
예를 들어 입력이 S = "helloworld", T = "hellorld"라면 출력은 8이 됩니다.
접근 방법
핵심 아이디어는 간단합니다. 두 문자열에 공통으로 등장하는 각 문자에 대해, 더 적게 등장한 횟수만큼 부분 수열에 포함할 수 있다는 점입니다. 따라서 각 문자열의 문자 빈도수를 계산한 뒤, 공통 문자별 최솟값을 모두 더하면 정답을 구할 수 있습니다.
- 빈 딕셔너리(맵) c와 d를 생성합니다.
- 문자열 a의 각 문자를 순회하며 c에 문자별 개수를 기록합니다.
- 문자열 b의 각 문자를 순회하며 d에 문자별 개수를 기록합니다.
- 결과 변수 res를 0으로 초기화합니다.
- c의 각 문자 ch에 대해 d에 해당 문자가 존재하면, res에 min(c[ch], d[ch]) 값을 더합니다.
- 모든 문자를 확인한 후 res를 반환합니다.
예제 코드
class Solution:
def solve(self, a, b):
c, d = {}, {}
for i in range(len(a)):
if a[i] in c:
c[a[i]] += 1
else:
c[a[i]] = 1
for i in range(len(b)):
if b[i] in d:
d[b[i]] += 1
else:
d[b[i]] = 1
res = 0
for ch in c:
if d.get(ch, 0) > 0:
res += min(c[ch], d[ch])
return res
ob = Solution()
S = "helloworld"
T = "hellorld"
print(ob.solve(S, T))
입력
S = "helloworld", T = "hellorld"
출력
8
동작 원리
S = "helloworld"에는 h:1개, e:1개, l:3개, o:2개, w:1개, r:1개, d:1개가 있고, T = "hellorld"에는 h:1개, e:1개, l:3개, o:1개, r:2개, d:1개가 있습니다. 공통 문자별 최솟값을 모두 더하면 1(h) + 1(e) + 3(l) + 1(o) + 1(r) + 1(d) = 8이 되므로 정답은 8입니다. 참고로 'w'는 T에 존재하지 않으므로 부분 수열에 포함되지 않습니다.
collections.Counter를 활용한 간결한 풀이
파이썬의 collections.Counter를 사용하면 같은 로직을 훨씬 짧게 작성할 수 있습니다. Counter 객체끼리 &(교집합) 연산자를 적용하면 각 문자의 최소 개수가 자동으로 계산됩니다.
from collections import Counter
class Solution:
def solve(self, a, b):
return sum((Counter(a) & Counter(b)).values())
ob = Solution()
S = "helloworld"
T = "hellorld"
print(ob.solve(S, T))
복잡도 분석
시간 복잡도는 두 문자열을 한 번씩 순회하므로 O(n + m)입니다. 공간 복잡도는 문자 종류가 소문자 알파벳으로 제한되므로 사실상 O(1)로 볼 수 있습니다.