[Algorism/HackerRank] Sherlock and Anagrams

👉 문제 링크

✏️ 문제 요약

• 주어진 문자열에서 Anagram 경우의 수가 되는 부분 문자열 찾기

  Anagram은 문자열 순서를 바꿔 동일한 철자로 이루어진 문자열 쌍을 말함
  ex:) abc == cba

• 단, 주어진 문자열의 순서를 변경한 경우의 수는 고려하지 않는다.

  현재 알고리즘 문제의 Anagram 조건이므로 다른 문제에서는 해당하지 않음
  주어진 문자열: abca 라고 했을 때, 임의로 caab와 같은 식으로 주어진 문자열을 변경하지는 않는다.

• 하지만 Anagram의 경우의 수가 되는 부분 문자열은 문자열 순서가 변경되어도 됨

  주어진 문자열: abca 에서 Anagram을 찾기 위한 부분 집합 비교로 [ab], [ac(= ca를 뒤집음)] 식으로 확인하는 비교는 가능함

💡 문제 풀이

• 1. Anagram이 가능한 부분 문자열은 순서를 변경하여 비교가 가능하므로, 고정된 순서로 정렬 후 비교하면 쌍을 이루는지 쉽게 비교 가능하다.
     따라서 모든 부분 문자열을 뽑아 알파벳 순서(오름차순, 내림차순 아무거나)를 정하여, 부분 문자열을 Key로 가진 해쉬맵으로 해당 문자열 개수를 카운팅 한다.

     알파벳 순서와 상관없이 카운팅하기 때문에 count > 1인 경우는 Anagram이 가능한 쌍이 존재한다.

• 2. 부분 문자열의 경우의 수는 카운트 수(n)개 중 2개를 뽑는 경우의 수(=수학 조합)와 같다.
     $\begin{pmatrix} n\\ 2 \end{pmatrix}$

     예시는 단일 문자열 a로만 나타내고, ab, abc처럼 다른 알파벳과 결합되어 있는 부분 문자열의 경우도 순서가 중요하지 않기 때문에 아래의 규칙과 동일하다.
     (n, m)은 index를 의미함

     • 주어진 문자열: aa

     1. a 가 1개인 문자열 수는 2개이므로, Anagram이 가능한 경우의 수는 2C2 ==> 1개
        (0, 1)
     2. a 가 2개인 문자열 수는 1개이므로, Anagram 쌍이 없음
        총: 1개
        
        

     • 주어진 문자열: aaa

     1. a 가 1개인 문자열 수는 3개이므로, Anagram이 가능한 경우의 수는 3C2 ==> 3개
        (0, 1), (0, 2), (1, 2)
     2. a 가 2개인 문자열 수는 2개이므로, Anagram이 가능한 경우의 수는 2C2 ==> 1개
        (0~1, 1~2)
     3. a 가 3개인 문자열 수는 1개이므로, Anagram 쌍이 없음
        총: 4개
        
        

     • 주어진 문자열: aaaa

     1. a 가 1개인 문자열 수는 4개이므로, Anagram이 가능한 경우의 수는 4C2 ==> 6개
        (0, 1), (0, 2), (0, 3), (1, 2), (1, 3), (2, 3)
     2. a 가 2개인 문자열 수는 3개이므로, Anagram이 가능한 경우의 수는 3C2 ==> 3개
        (0~1, 1~2), (0~1, 2~3), (1~2, 2~3)
     3. a 가 3개인 문자열 수는 2개이므로, Anagram이 가능한 경우의 수는 2C2 ==> 1개
        (0~2, 1~3)
     4. a 가 4개인 문자열 수는 1개이므로, Anagram 쌍이 없음
        총: 10개
        
        

3. 상기 2번을 어떻게 구현하냐에 따라 구현이 좀 더 간단해 질 수 있음
   구현 코드에서는 조합식이 등차수열의 합 공식과 동일하게 도출되어 등차수열의 합 공식을 사용함

💻 구현 코드

코드 보기

  public static int sherlockAndAnagrams(String s) {
      Map<String, Integer> countMap = new HashMap<>();

      for (int i = 0; i < s.length(); i++) {
          for (int j = i + 1; j < s.length() + 1; j++) {
              // 부분 문자열을 알파벳 오름차순 순서로 변경하여 새로운 부분 문자열을 생성
              String a = s.substring(i, j).chars()
                      .sorted()
                      .mapToObj(ch -> String.valueOf((char) ch))
                      .collect(Collectors.joining());
              
              // 부분 문자열을 카운팅하는 해쉬맵에 저장
              countMap.merge(a, 1, Integer::sum);
          }
      }

      // 카운팅된 수를 기준으로 2개를 뽑아 조합한 값이 개별 경우의 수
      // 각 개별 경우의 수를 합한 값이 총 문자열의 Anagram 경우의 수
      return countMap.values().stream()
              .filter(value -> value > 1)
              .mapToInt(value -> value * (value - 1) / 2)
              .sum();
  }