=========================================================================================
※ 문제 링크
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)
'지식이 늘었다' 카테고리의 다른 글
[cve-2019-9978] 특정 파라미터를 이용한 wordpress 원격 명령 실행 공격 (0) | 2019.06.07 |
---|---|
[Hackerrank - algorithm] Sherlock and the Valid String (0) | 2019.01.19 |
[Hackerrank - algorithm] Highest Value Palindrome (0) | 2019.01.19 |
[Hackerrank - algorithm] Array Manipulation (0) | 2018.12.03 |
[Hacker_rank - SQL] Projects (0) | 2018.11.14 |