문제 이해
두 개의 문자열 s와 t가 주어졌을 때, s에 포함된 문자들의 순서를 자유롭게 바꾸어(swap) t와 동일한 문자열을 만들 수 있는지 확인해야 합니다.
예를 들어 s = "worldlloeh", t = "helloworld"라고 한다면, s의 문자들을 적절히 재배열하여 "helloworld"를 만들 수 있으므로 결과는 True가 됩니다.
사실 이 문제는 두 문자열이 아나그램(anagram) 관계인지 판별하는 문제와 본질적으로 같습니다. 즉, 두 문자열이 같은 문자들을 정확히 같은 개수만큼 담고 있는지만 검증하면 됩니다.
풀이 접근 방법
s_len:s의 길이,t_len:t의 길이- 두 길이가 다르다면 문자 구성 자체가 같을 수 없으므로 즉시 False를 반환합니다.
freq:s의 모든 문자와 그 빈도수를 저장하는 맵(딕셔너리)을 생성합니다.t의 각 문자를 순회하면서 해당 문자의 빈도수를 1씩 차감합니다.- 차감한 값이 0보다 작아지면
t에 필요한 문자가s에 부족하다는 의미이므로 False를 반환합니다. - 모든 검사를 통과했다면 True를 반환합니다.
구현 예제
from collections import defaultdict
def solve(s, t):
s_len = len(s)
t_len = len(t)
if s_len != t_len:
return False
freq = defaultdict(int)
for char in s:
freq[char] += 1
for i in range(t_len):
freq[t[i]] -= 1
if freq[t[i]] < 0:
return False
return True
s = "worldlloeh"
t = "helloworld"
print(solve(s, t))
입력
"worldlloeh", "helloworld"
출력
True
복잡도 및 참고 사항
이 알고리즘은 두 문자열을 각각 한 번씩 순회하므로 시간 복잡도는 O(n), 공간 복잡도는 고유 문자의 종류 수에 비례하여 O(k)입니다.
참고로 sorted(s) == sorted(t)처럼 두 문자열을 정렬한 뒤 비교하는 더 간단한 방법도 있지만, 정렬에 드는 비용 때문에 시간 복잡도가 O(n log n)으로 늘어납니다. 따라서 대용량 문자열을 다룰 때는 위의 빈도수 기반 방식이 더 효율적인 선택입니다.