애너그램 판별, 정렬 대신 문자 빈도표를 쓰는 이유
두 문자열이 같은 글자로만 이루어졌는지(애너그램인지) 판별하는 방법은 크게 두 가지입니다. 하나는 두 문자열을 각각 정렬해서 문자열 자체를 비교하는 방식, 다른 하나는 문자별 등장 횟수를 세어 빈도표를 비교하는 방식입니다. 겉보기엔 결과가 같아 보이지만 시간복잡도와 구현상의 함정이 다릅니다. 애너그램 검사기의 실제 코드를 기준으로 어떤 방식을 쓰는지, 그리고 한글처럼 자모가 분리될 수 있는 문자에서 무엇을 조심해야 하는지 정리했습니다.
1. 정렬 비교: 가장 직관적이지만 느린 방법
가장 먼저 떠올리는 방법은 두 문자열을 각각 배열로 쪼개 정렬한 뒤 그 결과가 완전히 같은지 비교하는 것입니다. 예를 들어 "listen"을 정렬하면 "eilnst", "silent"를 정렬해도 똑같이 "eilnst"가 나오므로 애너그램이라고 판정합니다. 직관적이지만 정렬 자체가 비교 기반 정렬 알고리즘 기준 O(n log n)이 걸리고, 문자열이 길어질수록(예: 문서 전체를 비교하는 경우) 불필요하게 느려집니다. 구현도 간단해 보이지만 "정렬 순서"라는 중간 산출물을 만들기 위해 원본 배열을 통째로 복사하고 재배치하는 비용이 듭니다.
2. 빈도표 비교: 문자를 세기만 하면 끝나는 방법
두 번째 방법은 각 문자열을 한 번씩만 순회하면서 문자별 등장 횟수를 Map(또는 배열)에 누적한 뒤, 두 빈도표를 비교하는 것입니다. 정렬이 필요 없으므로 순회 자체는 O(n)이고, 빈도표 두 개를 비교하는 비용도 서로 다른 문자 종류 수(보통 알파벳 26개, 한글이어도 몇백 종류 수준)에 비례하므로 사실상 선형 시간에 가깝습니다. 애너그램 검사기의 실제 코드를 보면 정렬 관련 함수(sort)는 전혀 쓰지 않고, 아래와 같은 charFreq 함수로 빈도표를 만듭니다.
function charFreq(s){const m=new Map();for(const c of s)m.set(c,(m.get(c)||0)+1);return m;} — 문자열을 한 번 순회하며 Map에 등장 횟수를 누적합니다. 판정은 a.length===b.length로 길이를 먼저 확인한 뒤, 두 문자열에 등장한 모든 문자(합집합)에 대해 fa.get(c)!==fb.get(c)인 문자가 하나라도 있으면 애너그램이 아니라고 판정합니다.
3. 성능 차이가 실제로 체감되는 지점
단어 두세 개를 비교하는 정도라면 정렬이든 빈도표든 체감 차이는 없습니다. 차이가 벌어지는 지점은 입력이 길어질 때입니다. 예를 들어 1만 자짜리 텍스트 두 개를 비교한다고 하면, 정렬 방식은 각 문자열마다 약 1만×log₂(1만)≈133,000회 수준의 비교 연산이 필요한 반면, 빈도표 방식은 각 문자열을 1만 번씩만 순회하면 됩니다. 아래는 입력 길이에 따른 대략적인 연산 규모 비교입니다.
| 입력 길이(n) | 정렬 비교 O(n log n) | 빈도표 비교 O(n) |
|---|---|---|
| 10자 | 약 33회 | 10회 |
| 1,000자 | 약 9,966회 | 1,000회 |
| 10,000자 | 약 132,877회 | 10,000회 |
입력이 길수록 격차가 벌어지는 이유는 정렬이 매 원소 비교마다 로그 배수만큼 더 많은 작업을 하기 때문입니다. 짧은 단어 게임용 애너그램 체크에서는 큰 의미가 없지만, 텍스트 전체나 로그 파일처럼 긴 입력을 다루는 도구라면 빈도표 방식이 명백히 유리합니다.
4. 한글에서 진짜 조심해야 할 함정: 자모 분리(NFC/NFD)
빈도표 방식이든 정렬 방식이든, 한글을 다룰 때 진짜 함정은 알고리즘이 아니라 "문자 하나가 실제로 몇 개의 유니코드 코드 포인트로 이루어져 있는가"입니다. 완성형 한글(NFC, Normalization Form C)로 저장된 "가"는 코드 포인트 하나이지만, 분해형(NFD, Normalization Form D)으로 저장된 "가"는 자음 "ㄱ"과 모음 "ㅏ"라는 코드 포인트 두 개로 쪼개져 있습니다. 겉보기엔 똑같이 "가"로 보여도 내부 표현이 다르면 문자 단위 순회 결과가 완전히 달라집니다. macOS 파일시스템이나 일부 입력기에서 NFD로 저장된 텍스트를 그대로 붙여넣으면 이런 문제가 생길 수 있습니다.
.normalize() 호출 없이 for(const c of s)로 문자열을 코드 포인트 단위로 순회합니다. 즉 입력이 이미 완성형(NFC)이면 "가", "나" 같은 음절이 정확히 한 글자로 세어지지만, 만약 어떤 경로로든 분해형(NFD) 텍스트가 들어오면 자음·모음이 각각 별도 문자로 집계되어 같은 단어인데도 다른 문자 구성으로 판정될 수 있습니다. 일반적인 키보드 입력·복사붙여넣기는 대부분 NFC이므로 실사용에서 문제가 되는 경우는 드물지만, 정규화를 명시적으로 보장하는 코드는 아닙니다.
5. 옵션 처리도 정규식 하나로: 구두점·공백·대소문자
이 도구는 비교 전에 옵션에 따라 대소문자·공백·구두점을 정규화합니다. 구두점 제거는 /[^\p{L}\p{N}]/gu라는 유니코드 속성 정규식을 쓰는데, \p{L}은 "문자"(알파벳뿐 아니라 한글·한자 포함), \p{N}은 "숫자"를 뜻합니다. 즉 영문 구두점만 걸러내는 게 아니라 언어에 상관없이 진짜 구두점·기호만 제거하도록 설계되어 있어, 한국어 문장에서도 정확히 동작합니다. 만약 텍스트 전체의 특수문자를 별도로 정리하고 싶다면 중복 줄 제거기나 유니코드 검사기로 원본 텍스트 구조를 먼저 확인하는 것도 방법입니다.
자주 묻는 질문
Q. 짧은 단어 비교라면 정렬 방식을 써도 상관없나요?
A. 네. "listen"과 "silent"처럼 몇 글자 안 되는 단어라면 정렬이든 빈도표든 실행 시간 차이는 사실상 없습니다. 성능 차이는 입력이 수백~수천 자 이상으로 길어질 때부터 체감됩니다.
Q. 빈도표 방식이 항상 메모리도 더 적게 쓰나요?
A. 꼭 그렇진 않습니다. 정렬 방식은 정렬된 배열(길이 n) 하나만 있으면 되지만, 빈도표 방식은 서로 다른 문자 종류마다 Map 항목이 하나씩 생깁니다. 다만 문자 종류 수는 대개 문자열 길이 n보다 훨씬 작으므로(알파벳 26개, 한글 음절이라 해도 실사용 범위에서는 수백 개 수준) 실질적으로는 빈도표 쪽이 더 가볍습니다.
Q. 이모지처럼 여러 코드 포인트로 이루어진 문자도 정확히 세어지나요?
A. 대부분의 유니코드 코드 포인트는 정확히 처리되지만, 국기 이모지나 ZWJ(Zero Width Joiner)로 결합된 이모지처럼 여러 코드 포인트가 하나의 시각적 문자로 보이는 경우엔 코드 포인트 단위로 쪼개져 집계되므로 예상과 다른 결과가 나올 수 있습니다. 한글 자모 분리(NFD)와 근본적으로 같은 종류의 함정입니다.
Q. 애너그램과 팰린드롬은 같은 방식으로 검사하나요?
A. 아니요. 애너그램은 서로 다른 두 문자열이 같은 문자 구성을 가지는지 검사하는 것이고, 팰린드롬은 문자열 하나가 앞으로 읽으나 뒤로 읽으나 같은지 검사하는 것이라 판정 로직 자체가 다릅니다. 팰린드롬 여부는 팰린드롬 검사기로 확인할 수 있습니다.