본문 바로가기

지식이 늘었다

[Hackerrank - algorithm] Sherlock and Anagrams

=========================================================================================

※ 문제 링크

https://www.hackerrank.com/challenges/sherlock-and-anagrams/problem?h_l=interview&playlist_slugs%5B%5D=interview-preparation-kit&playlist_slugs%5B%5D=dictionaries-hashmaps

=========================================================================================


q개의 문자열을 입력받았을 때 각각 문자열에서 anagram* 쌍의 갯수를 출력해주는 문제

* anagram :  한 단어의 철자를 분해해 다른 단어, 혹은 다른 문장으로 바꾸는 것

ex) abcd -> dcba


예를 들어, mom이란 문자열을 입력받으면 

[m, m], [mo, om] 이란 anagram 쌍을 만들 수 있기 때문에 2를 출력해야 한다.


나의 경우는 n개의 경우에서 2개를 뽑는 것을 핵심으로 생각

(n combination 2 , nC2 -> n(n-1) / 2 )


나의 문제 해결 프로세스는 다음과 같다


1) 문자열에서 모든 가능한 부분집합들을 정렬하여 저장 -> O(nm) * sort 시간 -> 약 O(n^3logn)

 ex) abab -> {a, b, a, b, ab, ab, ab, aab, abb} -> {a: 2, b: 2, ab : 3, aab : 1, abb : 1}

 

2. values값들을 nC2 하여 더함 -> O(n)