문제 설명

두 단어가 서로 애너그램 관계라는 것은
문자의 순서를 바꾸면 같은 단어가 될 수 있는 경우를 의미한다.

예시

occurs ↔ succor

문자 순서를 바꾸면 서로 같은 단어가 된다.

하지만 어떤 단어들은 애너그램이 아니더라도
일부 문자를 제거하면 애너그램이 될 수 있다.

예시

dared
bread

여기서

dared → d 제거 → ared
bread → b 제거 → read

ared와 read는 애너그램이 된다.

따라서 문제는

두 단어가 애너그램이 되도록 만들기 위해
제거해야 하는 최소 문자 개수를 구하는 것이다.

---

입력 조건

• 두 줄에 영어 소문자로 이루어진 단어가 입력된다.
• 단어의 길이는 최대 1000
• 최소 길이는 1

---

출력

애너그램 관계가 되도록 만들기 위해
제거해야 하는 문자 개수의 최소값을 출력한다.

---

예제 입력

aabbcc
xxyybb

예제 출력

8

---

문제 해결 아이디어

두 문자열이 애너그램이 되려면
각 알파벳의 개수가 동일해야 한다.

예를 들어

aabbcc
xxyybb

각 문자 개수를 비교하면

문자	첫 번째 문자열	두 번째 문자열
a	2	0
b	2	2
c	2	0
x	0	2
y	0	2

차이만큼 문자를 제거해야 한다.

즉

|countA - countB|

를 모든 문자에 대해 더하면
제거해야 할 최소 문자 개수가 된다.

---

수업 풀이 방식 (알파벳 카운트)

이 방법은 문자 개수를 배열로 저장하는 방식이다.

알파벳이 26개이므로

int[26]

배열을 사용한다.

코드

import java.util.*;

public class Main {

    public static void main(String[] args) {

        Scanner sc = new Scanner(System.in);

        String a = sc.next();
        String b = sc.next();

        int[] countA = new int[26];
        int[] countB = new int[26];

        for (int i = 0; i < a.length(); i++)
            countA[a.charAt(i) - 'a']++;

        for (int i = 0; i < b.length(); i++)
            countB[b.charAt(i) - 'a']++;

        int ans = 0;

        for (int i = 0; i < 26; i++) {
            ans += Math.abs(countA[i] - countB[i]);
        }

        System.out.println(ans);
    }
}

---

핵심 개념

1. 문자 → 인덱스 변환

알파벳은 다음과 같이 숫자로 변환할 수 있다.

'a' = 0
'b' = 1
...
'z' = 25

방법

문자 - 'a'

예

'a' - 'a' = 0
'b' - 'a' = 1
'c' - 'a' = 2

그래서

count[문자 - 'a']

형태로 알파벳 개수를 셀 수 있다.

---

2. 절댓값 차이 계산

두 문자열의 문자 개수 차이는

Math.abs(a - b)

로 계산한다.

예

a: 3
b: 1

|3 - 1| = 2

2개의 문자를 제거해야 한다는 의미이다.

---

내가 작성한 풀이 방식

문자를 직접 비교하면서
같은 문자가 발견되면 제거하는 방식이다.

코드

import java.util.*;

public class Main {

    public static void main(String[] args) {

        Scanner sc = new Scanner(System.in);

        String input = sc.nextLine();
        String input2 = sc.nextLine();

        int count = 0;
        char[] arr = input2.toCharArray();

        for (char a : input.toCharArray()) {
            for (int i = 0; i < arr.length; i++) {

                if (a == arr[i]) {
                    count++;
                    arr[i] = ' ';
                    break;
                }

            }
        }

        int result = input.length() + input2.length() - 2 * count;

        System.out.println(result);

    }

}

---

두 풀이의 차이

방식	특징
문자 개수 카운트	시간복잡도 O(N)
문자 직접 비교	시간복잡도 O(N²)

문자열 길이가 최대 1000이므로
둘 다 통과하지만

일반적으로는

알파벳 카운트 방식

이 더 효율적인 방법이다.

---

시간 복잡도

카운트 방식

O(N)

문자 비교 방식

O(N²)

---

정리

이 문제의 핵심은 다음과 같다.

1. 두 문자열의 알파벳 개수를 비교한다.
2. 각 문자 개수 차이의 절댓값을 더한다.
3. 그 값이 제거해야 할 최소 문자 개수가 된다.

문자열 문제에서 자주 등장하는
알파벳 카운트 패턴을 이해할 수 있는 대표적인 문제이다.