두 개의 문자열 s와 t가 주어졌을 때, 문자열 t가 s에 포함된 문자들을 사용하여 구성될 수 있는지 확인해야 합니다.
예를 들어, s = "owleh"이고 t = "hello"라면, s의 문자들을 조합하여 "hello"를 만들 수 있으므로 출력은 True가 됩니다.
문제 해결 접근 방법
이 문제는 문자 빈도수 카운팅을 통해 효율적으로 해결할 수 있습니다. 핵심 아이디어는 다음과 같습니다.
- s의 각 문자별 등장 횟수를 저장하는 맵(freq)을 생성합니다.
- t의 각 문자를 순회하면서, 해당 문자의 남은 개수가 0이라면 필요한 문자가 부족한 것이므로 False를 반환합니다.
- 사용 가능한 경우에는 해당 문자의 개수를 1만큼 감소시킵니다.
- t의 모든 문자를 성공적으로 배치했다면 True를 반환합니다.
예제 코드
from collections import defaultdict
def solve(s, t):
freq = defaultdict(int)
# 문자열 s의 각 문자 빈도수 계산
for i in range(len(s)):
freq[s[i]] += 1
# 문자열 t를 만들 수 있는지 확인
for i in range(len(t)):
if freq[t[i]] == 0:
return False
freq[t[i]] -= 1
return True
s = "owhtlleh"
t = "hello"
print(solve(s, t))
입력 및 출력 결과
입력: s = "owhtlleh", t = "hello" 출력: True
코드 설명
defaultdict(int)를 사용하면 존재하지 않는 키에 접근할 때 자동으로 값이 0으로 초기화되므로, 별도의 예외 처리 없이 문자별 빈도수를 손쉽게 관리할 수 있습니다.
먼저 첫 번째 반복문에서 s의 각 문자 개수를 세고, 이후 두 번째 반복문에서 t의 문자를 하나씩 확인하며 사용 가능 여부를 검사합니다. t의 어떤 문자라도 s에서 더 이상 사용할 수 없다면 즉시 False를 반환하고, 모든 문자를 문제없이 배치하면 True를 반환합니다.
시간 복잡도
두 문자열을 각각 한 번씩 순회하므로 시간 복잡도는 O(n + m)입니다. 여기서 n은 s의 길이, m은 t의 길이를 의미합니다.
참고: collections.Counter를 활용한 간결한 풀이
Python의 collections.Counter를 사용하면 동일한 로직을 더욱 간결하게 작성할 수 있습니다.
from collections import Counter
def solve(s, t):
sc = Counter(s)
tc = Counter(t)
return all(sc[ch] >= cnt for ch, cnt in tc.items())
s = "owhtlleh"
t = "hello"
print(solve(s, t)) # True