[알고리즘][문자열] 애너그램(Anagram) 핵심 정리

1. 애너그램이란?

• 정의:
  두 단어(또는 문장)가 같은 알파벳을 같은 개수로 가지고 순서만 다르게 배치된 경우를 말함
  (예: "listen" ↔ "silent", "Dormitory" ↔ "Dirty room")

---

2. 애너그램 판별 기본 원칙

1. 알파벳만 비교한다 (공백, 숫자, 특수문자 등은 모두 무시)
2. 대소문자 구분 없음 (모두 소문자 혹은 대문자로 변환 후 비교)
3. 각 문자의 개수가 동일해야 함

---

3. 자바에서 입력 전처리 방법

• 알파벳 이외 문자 제거:
  s = s.replaceAll("[^a-zA-Z]", "");
• 대소문자 통일:
  s = s.toLowerCase();
• 모든 공백 제거:
  위의 정규표현식에서 자동 처리됨
• 알파벳만으로 이루어져 있는지 검증 (필요할 경우):
  s.matches("[a-zA-Z]+")

---

4. 애너그램 구현 대표 방식

① 문자 정렬로 비교

• 알파벳 정렬 후 배열이 같으면 애너그램

String s1 = ...;
String s2 = ...;
s1 = s1.replaceAll("[^a-zA-Z]", "").toLowerCase();
s2 = s2.replaceAll("[^a-zA-Z]", "").toLowerCase();

if (s1.length() != s2.length()) return false;

char[] arr1 = s1.toCharArray();
char[] arr2 = s2.toCharArray();
Arrays.sort(arr1);
Arrays.sort(arr2);
return Arrays.equals(arr1, arr2);

---

② 문자 개수(빈도수)로 비교

• 각 알파벳이 몇 번 나오는지 카운트해서 비교

Map<Character, Integer> map = new HashMap<>();
for (char c : s1.toCharArray()) map.put(c, map.getOrDefault(c, 0) + 1);
for (char c : s2.toCharArray()) map.put(c, map.getOrDefault(c, 0) - 1);
for (int count : map.values()) if (count != 0) return false;
return true;

 

 

---

5. 정규표현식에서의 기호 의미

• [a-zA-Z] : 영문자 한 글자
• [^a-zA-Z] : 영문자가 아닌 모든 문자
• + : 1개 이상 반복
• \\s : 공백 문자(스페이스, 탭, 개행 등)
• * : 0개 이상 반복

---

6. 자주 쓰는 문자열 처리 코드

• 모든 공백 제거:
  s.replaceAll("\\s+", "")
• 공백을 기준으로 단어 배열:
  s.split("\\s+")

---

7. 정리 및 실무 팁

• 애너그램 판별 전에는 항상 입력을 전처리(불필요한 문자 제거, 소문자 변환)
• 입력값 유효성(알파벳만 구성 여부) 검사도 실무에서는 추가하는 것이 안전
• 문제 조건에 따라 특수문자/공백/숫자 처리를 다르게 할 수 있으니 명확히 확인