두 개의 문자열 s와 t가 주어졌을 때, s에 포함된 각 문자의 등장 횟수(빈도)가 t에서 같은 문자의 등장 횟수에 대해 배수 또는 약수 관계를 만족하는지 확인해야 합니다.
예를 들어 입력이 s = "xxyzzw", t = "yyyxxxxzz"라면 결과는 True가 됩니다. 그 이유는 다음과 같습니다.
- x는 s에서 2번, t에서 4번 등장하며, 4는 2의 배수이므로 조건을 만족합니다.
- y는 s에서 1번, t에서 3번 등장하며, 3은 1의 배수이므로 조건을 만족합니다.
- z는 s와 t 양쪽에서 모두 2번씩 등장하므로 조건을 만족합니다.
- w는 s에만 존재하고 t에는 없으므로 비교 대상에서 제외됩니다.
문제 해결 접근 방법
이 문제는 다음 단계를 따라 해결할 수 있습니다.
- s_freq := s의 모든 문자와 각각의 빈도를 저장한 맵을 만듭니다.
- t_freq := t의 모든 문자와 각각의 빈도를 저장한 맵을 만듭니다.
- s_freq의 각 문자 ch에 대해 다음을 수행합니다.
- ch가 t_freq에 없다면 다음 반복으로 넘어갑니다.
- t_freq[ch]가 s_freq[ch]로 나누어떨어지거나, s_freq[ch]가 t_freq[ch]로 나누어떨어진다면 다음 반복으로 넘어갑니다.
- 위 조건을 만족하지 않으면 False를 반환합니다.
- 모든 문자가 검사를 통과하면 True를 반환합니다.
예제 코드
아래 구현을 통해 더 자세히 이해할 수 있습니다.
from collections import defaultdict
def solve(s, t):
s_freq = defaultdict(int)
t_freq = defaultdict(int)
for i in range(len(s)):
s_freq[s[i]] += 1
for i in range(len(t)):
t_freq[t[i]] += 1
for ch in s_freq:
if ch not in t_freq:
continue
if t_freq[ch] % s_freq[ch] == 0 or s_freq[ch] % t_freq[ch] == 0:
continue
else:
return False
return True
s = "xxyzzw"
t = "yyyxxxxzz"
print(solve(s, t))입력
"xxyzzw", "yyyxxxxzz"
출력
True
추가 팁: Counter 활용하기
파이썬의 collections.Counter를 사용하면 빈도 계산 과정을 더욱 간결하게 처리할 수 있습니다.
from collections import Counter
def solve(s, t):
s_freq = Counter(s)
t_freq = Counter(t)
for ch, cnt in s_freq.items():
if ch not in t_freq:
continue
if t_freq[ch] % cnt != 0 and cnt % t_freq[ch] != 0:
return False
return True이 알고리즘의 시간 복잡도는 두 문자열 길이의 합에 비례하는 O(n + m)이며, 공간 복잡도 역시 고유 문자 수에 비례하므로 매우 효율적입니다.