애너그램 짝꿍 찾기
실버 I의견: 0
리세는 국어 시간에 배운 애너그램 놀이에 푹 빠졌다. 두 단어가 서로의 글자를 재배열해서 만들 수 있으면 (예: listen 과 silent) 두 단어는 애너그램이다.
단어 \(N\)개가 주어질 때, 서로 애너그램인 단어 쌍 \((i, j)\) (\(i < j\)) 의 개수를 구하여라. 같은 단어가 여러 번 주어질 수도 있으며, 완전히 같은 두 단어도 애너그램 쌍으로 센다.
\(N\)이 최대 \(100\,000\)이므로, 모든 쌍을 직접 비교하면 시간 안에 풀 수 없다. 각 단어를 적절한 키로 바꿔 같은 키끼리 묶어 세어 보자.
- \(1 \le N \le 100\,000\)
- 각 단어는 길이 \(1\) 이상 \(20\) 이하의 영문 소문자 문자열이다.
첫째 줄에 단어의 개수 \(N\)이 주어진다.
다음 \(N\)개의 줄에 영문 소문자로만 이루어진 단어가 한 줄에 하나씩 주어진다. 각 단어의 길이는 \(1\) 이상 \(20\) 이하이다.
서로 애너그램인 단어 쌍의 개수를 출력한다.
5
listen
silent
enlist
cat
act4listen-silent-enlist가 서로 애너그램이라 3쌍, cat-act가 1쌍으로 총 4쌍이다.
4
abc
abd
abe
abf0어떤 두 단어도 서로 애너그램이 아니므로 0쌍이다.
막혔나요? 코인으로 단계별 힌트를 잠금 해제하세요 — 첫 힌트는 가벼운 방향 제시, 뒤로 갈수록 더 많이 알려 줍니다. 문제를 풀면 모든 힌트가 무료로 공개됩니다.
riseoj 작성
출처 Original
평가 및 의견
애너그램 짝꿍 찾기
아직 의견이 없습니다. 자격이 된다면 위 양식에서 가장 먼저 평가해 보세요.
풀이 제출
애너그램 짝꿍 찾기