두 개의 문자열 s와 t가 주어졌을 때, s에서 가장 자주 등장하는 문자를 찾은 뒤, 그 문자가 t에도 정확히 같은 횟수만큼 나타나는지 확인해야 합니다.
예를 들어 입력이 s = "crosssection", t = "securesystem"이라면 결과는 True가 됩니다. s에서 가장 빈도가 높은 문자는 's'이며, t에도 's'가 정확히 같은 횟수만큼 존재하기 때문입니다.
문제 해결 접근 방법
이 문제는 다음 단계를 따라 해결할 수 있습니다.
- freq := s의 모든 문자와 각 문자의 빈도를 저장하는 맵(딕셔너리) 생성
- max_freq_char := s에서 빈도가 가장 높은 문자
- max_freq := max_freq_char의 빈도 값
- t에서 max_freq_char가 나타나는 횟수가 max_freq와 같으면 True 반환
- 그렇지 않으면 False 반환
이 알고리즘의 시간 복잡도는 O(n + m)입니다. 여기서 n은 문자열 s의 길이, m은 문자열 t의 길이를 의미하며, 각 문자열을 한 번씩만 순회하면 되기 때문에 매우 효율적입니다.
예제 코드
아래 파이썬 구현 예시를 통해 더 잘 이해할 수 있습니다.
from collections import defaultdict
def solve(s, t):
freq = defaultdict(int)
for char in s:
freq[char] += 1
max_freq_char = max(freq, key=freq.get)
max_freq = freq[max_freq_char]
if max_freq == t.count(max_freq_char):
return True
return False
s = "crosssection"
t = "securesystem"
print(solve(s, t))입력
"crosssection", "securesystem"
출력
True
코드 설명
defaultdict(int)를 사용하면 처음 등장하는 문자에 대해 별도의 초기화 없이 바로 빈도를 1부터 증가시킬 수 있습니다. max(freq, key=freq.get)는 딕셔너리의 키 중 값(빈도)이 가장 큰 키, 즉 최다 빈도 문자를 반환합니다. 마지막으로 파이썬 내장 메서드인 t.count()를 활용해 해당 문자가 t에 나타나는 횟수를 손쉽게 구할 수 있습니다.