[Hackerrank] Sherlock and Anagrams

코딩테스트

[Hackerrank] Sherlock and Anagrams

essay0263 2025. 1. 27. 00:17

문제: 애너그램 찾기

문제 설명
두 문자열이 애너그램(anagram)이라는 것은, 한 문자열의 문자를 재배열하여 다른 문자열로 만들 수 있음을 의미합니다. 주어진 문자열에서, 애너그램 관계를 이루는 모든 부분 문자열 쌍의 개수를 구하세요.

예시
문자열 s = "mom"이 주어졌을 때, 애너그램을 이루는 부분 문자열 쌍은 다음과 같습니다:

[m, m]: 인덱스 [0], [2]
[mo, om]: 인덱스 [0, 1], [1, 2]

결과적으로, 애너그램을 이루는 쌍의 총 개수는 3입니다.

함수 설명
함수 sherlockAndAnagrams를 완성하세요. 이 함수는 다음의 매개변수를 입력받습니다:

s(문자열): 애너그램을 찾을 문자열.

출력값
애너그램 관계를 이루는 모든 부분 문자열 쌍의 개수를 정수로 반환하세요.

입력 형식

문자열 s는 소문자 알파벳(a-z)만 포함합니다.
2 ≤ len(s) ≤ 100

예시 입력 및 출력

입력:

s = "abba"

출력:

설명:
다음과 같은 애너그램 쌍이 존재합니다:

[a, a]
[ab, ba]
[b, b]
[abb, bba]

총 4개의 쌍이 존재합니다.

먼저 탐색하는 글자의 범위(k)를 1부터 전체 길이 - 1까지 설정했다. 그리고 이중 루프를 이용해 탐색 범위(i와 j)를 설정했는데, 첫번째 탐색(i)는 0 부터 (전체 길이 - 탐색 범위(k))까지 탐색을 하고, 두번째 탐색(j) (i + 1)부터 (전체 길이 - 탐색 범위(k))까지 탐색을 한다. 문자열들은 Counter를 이용해서 글자의 빈도를 비교했다. 만약 2개의 Counter가 동일하면 2개의 글자 구성은 동일하다는 뜻이니 ans의 값을 1 증가 시켜주어서 총 개수를 세는 방식을 이용했다. 코드는 다음과 같다.

def sherlockAndAnagrams(s):
    ans = 0
    for k in range(1, len(s)):
        for i in range(0, len(s) - k):
            for j in range(i + 1, len(s) - k + 1):
                if Counter(s[i:i + k]) == Counter(s[j:j + k]):
                    print(f"Counter(s[i:i + k]) = {Counter(s[i:i + k])}, Counter(s[j:j + k])")
                    ans += 1
    return ans

비록 O(n^3)의 복잡도를 가지지만, s의 길이가 최대 100까지 밖에 안되기 때문에 해당 방법이 통한다고 생각했다. 그러나 이 방법은 시간 초과를 일으켰기 때문에 다른 방법을 알아보았다.

그래서 해시맵(딕셔너리)를 이용한 방법을 생각하였다. anagram_dict라는 딕셔너리를 선언하고, 모든 부분 문자열을 정렬된 형태로 변환하고 딕셔너리에 저장한다. 딕셔너리의 키는 정렬된 문자열이고, 값은 해당 문자열의 등장 횟수이다. 동일한 애너그램의 문자열이 등장할 때 마다 등장 횟수를 기반으로 쌍의 개수를 계산하는 방식을 이용했다. 예를 들어서 aa라는 문자열이 총 4번 등장하였으면, 이 문자열로 만들 수 있는 애너그램 쌍의 개수는 4개 중 2개를 고르는 경우의 수, 즉 4C2(조합)이다. 조합의 값은 1 + 2 + 3 = 6 이므로 각 단계에서 등장하는 횟수만큼 쌍을 추가해주면 계산할 수 있다.

해당 방식을 구현한 부분은 다음과 같다.

tmp = "".join(sorted(s[j:j + i]))
if tmp in anagram_dict.keys():
    ans += anagram_dict[tmp]#기존 값만큼 쌍 추가
    anagram_dict[tmp] += 1 # 등장 횟수 증가
else:
    anagram_dict[tmp] = 1 #새로운 키 추가

이 방식을 이용하면 시간 복잡도는 O(n^2)이 나오고, 시간 초과 문제를 해결할 수 있게 된다. 전체적인 코드는 다음과 같다.

def sherlockAndAnagrams(s):
    ans = 0
    anagram_dict = {}
    for i in range(1, len(s)):
        for j in range(len(s) - i + 1):
            tmp = "".join(sorted(s[j:j + i]))
            if tmp in anagram_dict.keys():
                ans += anagram_dict[tmp]
                anagram_dict[tmp] += 1
            else:
                anagram_dict[tmp] = 1
    print(anagram_dict)
    return ans