HackerRank : Sherlock and Anagrams (Java)

문제 링크

The problem link : Sherlock and Anagrams

문제 요약

n개의 문자열이 주어졌을때, 각 문자열마다 애너그램을 통해 서로 같은 문자열을 만들 수 있는 쌍의 개수를 찾으세요.
(* 애너그램 : 재배열을 했을때 다른 뜻의 문자를 만듦)

애너그램의 예시는 다음과 같습니다.

s = mom
[m,m] [mo,om] -> 2개의 정답

문제 풀이

핵심 코드는 다음과 같습니다.

    public static void add(HashMap<String,Integer> hm, String s){ // 3
        char a[] = s.toCharArray();
        Arrays.sort(a); // (1)
        ns = new String(a);
        hm.putIfAbsent(ns,0); // (2)
        hm.put(s, hm.get(ns)+1); // (3)
    }

    public static int sherlockAndAnagrams(String s) {
    HashMap <String, Integer> hm = new HashMap<>(); // 1
    int ans = 0;

    for(int i=0; i<s.length(); i++){ 
        for(int j=i+1; j<=s.length(); j++){
            add(hm, s.substring(i,j)); // 2
        }
    }
    for(int k:hm.values()){ // 4
        ans += (k*(k-1))/2;
    }
    return ans;
    }

1. HashMap으로 변수를 생성합니다. 애너그램으로 같은 문자열을 만들 수 있는 문자열 String과 그것의 쌍의 개수를 저장한 Integer로 HashMap을 생성합니다.
2. 2중 for문을 통해 문자열 s의 i번째에서 j-1번째까지의 문자들 중 정답의 개수를 찾기위해 add라는 메서드로 탐색을 시작합니다.
3. (1) 문자열 s를 문자 타입으로 쪼개서 저장한 뒤, 오름차순으로 정렬합니다. 그런 다음 정렬된 문자 타입의 배열을 새로운 문자열 ns로 만듭니다.
   (2) 오름차순으로 정렬된 새로운 문자열 ns가 hm에 없을 경우, 0의 개수로 새로이 저장해줍니다.
   여기서 사용되는 putIfAbsent는 key값이 존재할경우 key값을 반환해주고, 그렇지 않을 경우 key와 value 쌍을 HashMap에 저장해주고 null을 반환합니다.
   (3) 오름차순으로 정렬된 새로운 문자열 ns를 hm에 (기존에 존재했던 value의) 1을 더하여 저장해줍니다.
4. hm에서 모든 value의 값을 (x*(x-1))/2 하여 더해줍니다.
   이렇게하는 이유는 아래의 예시와 같습니다.

s = kkkkkk
여기서 'k' 문자로 정답이 가능한 개수는 15개 입니다.
1. 첫 번째 k / 나머지 kkkkk -> 5개
2. 두 번째 k / 나머지 kkkk -> 4개 (첫 번째 k와는 이미 쌍이 이루어졌으므로 포함X)
3. 세 번째 k / 나머지 kkk -> 3개 (")
4. 네 번째 k / 나머지 kk -> 2개 (")
5. 다섯번 째 k / 나머지 k -> 1개 (")
= 총합 15개

그런 다음 합산된 정답을 출력해줍니다.

시간 복잡도

O(n2) 입니다.
HashMap에서 value로 값을 찾는건 O(n)이지만, 중간에 2중 for문을 돌리는 부분이 있으므로 위 코드의 시간복잡도는 O(n2) 입니다.