소문자로만 이루어진 문자열이 하나 주어졌다고 가정해 봅시다. 이때 확인해야 할 것은, 문자열을 중간에서 잘랐을 때 양쪽 두 절반이 최소 한 가지 이상의 차이를 가지는지 여부입니다. 여기서 '차이'란 양쪽에 서로 다른 문자가 존재하는 경우 또는 동일한 문자라도 등장 횟수(빈도)가 다른 경우를 모두 포함합니다. 만약 문자열 길이가 홀수라면, 정중앙의 문자 하나는 무시하고 나머지 문자들만 대상으로 검사합니다.
예를 들어 입력이 s = "helloohekk"라고 해보겠습니다. 이 경우 출력값은 True가 됩니다. 왼쪽 절반은 "hello", 오른쪽 절반은 "ohekk"인데, 두 부분이 서로 다르기 때문입니다.
해결 접근 방법
이 문제는 좌우 절반의 문자 빈도를 각각 계산한 뒤 비교하는 방식으로 해결할 수 있습니다. 구체적인 단계는 다음과 같습니다.
- left_freq := 비어 있는 맵(딕셔너리) 생성
- right_freq := 비어 있는 맵 생성
- n := 문자열 s의 길이
- i를 0부터 n//2 - 1까지 반복하며 left_freq[s[i]] 값을 1씩 증가
- i를 n//2부터 n-1까지 반복하며 right_freq[s[i]] 값을 1씩 증가
- s의 모든 문자 char에 대해 다음을 수행:
- right_freq[char]와 left_freq[char]가 다르면 True 반환
- 모든 문자의 빈도가 일치하면 False 반환
구현 예제
아래 코드를 통해 더 명확하게 이해할 수 있습니다.
from collections import defaultdict def solve(s): left_freq = defaultdict(int) right_freq = defaultdict(int) n = len(s) for i in range(n//2): left_freq[s[i]] += 1 for i in range(n//2, n): right_freq[s[i]] += 1 for char in s: if right_freq[char] != left_freq[char]: return True return False s = "helloohekk" print(solve(s))
입력
"helloohekk"
출력
True
동작 원리와 복잡도
이 알고리즘의 핵심은 collections.defaultdict를 활용해 존재하지 않는 키에 접근하더라도 자동으로 0으로 초기화되도록 한다는 점입니다. 덕분에 별도의 예외 처리 없이 깔끔하게 빈도 카운팅을 수행할 수 있습니다.
시간 복잡도를 살펴보면, 문자열을 한 번 순회하며 좌우 빈도를 계산하는 데 O(n), 전체 문자를 다시 한 번 비교하는 데 O(n)이 걸리므로 전체 시간 복잡도는 O(n)입니다. 공간 복잡도 역시 최대 알파벳 종류 수(26개)만큼의 저장 공간을 사용하므로 O(1)로 볼 수 있습니다. 따라서 길이가 매우 긴 문자열에 대해서도 효율적으로 동작합니다.