시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
---|---|---|---|---|---|
1 초 | 256 MB | 1173 | 512 | 416 | 50.363% |
만약 단어 A의 알파벳 순서를 바꿔서 단어 B를 만들 수 있다면, 두 단어는 애너그램이라고 한다. 예를 들어, occurs는 succor의 애너그램이지만, dear는 dared의 애너그램이 아니다. 영어에서 가장 유명한 애너그램은 dog와 god이다.
두 단어의 애너그램 거리란, 두 단어가 애너그램이 되기 위해서 지워야하는 단어의 최소 개수이다. 예를 들어, sleep과 leap이 주어졌다면, sleep에서 2개, leap에서 1개를 지운다면 두 단어는 애너그램 관계가 된다. 따라서, sleep과 leap의 애너그램 거리는 3이다. 서로 공통된 알파벳이 없는 dog와 cat같은 경우에는 모든 단어를 지워야 하기 때문에, 애너그램 거리가 6이다.
두 단어가 주어졌을 때, 두 단어의 애너그램 거리를 구하는 프로그램을 작성하시오.
첫째 줄에 테스트 케이스의 개수 N이 주어진다. N은 60,000보다 작거나 같은 자연수이다. 각 테스트 케이스는 두 줄로 이루어져 있고, 한 줄에 단어가 하나씩 주어진다.
단어의 길이는 0일 수도 있고, 알파벳 소문자로만 이루어져 있다. 단어는 실제로 영어 사전에 있는 단어만 주어지며, 영어 사전에서 가장 긴 단어는 pneumonoultramicroscopicsilicovolcanoconiosis이다.
각 테스트 케이스에 대해서 케이스 번호와 입력으로 주어진 두 단어의 애너그램 거리를 출력한다.
4 crocus succor dares seared empty smell lemon
Case #1: 0 Case #2: 1 Case #3: 5 Case #4: 4
ICPC > Regionals > Europe > Southeastern European Regional Contest > SEERC 2005 H번