[BaekJoon] #1919 - 애너그램 만들기 [Java][C++]

문제 링크

---

1. 아이디어

애너그램 관계는 두 단어의 철자의 순서를 맘대로 바꿔서 같아질 수 있는 관계로 애너그램 관계에 있으려면 각 단어가 가지고 있는 철자의 종류와 개수가 동일하면 된다. 따라서 알파벳에 대한 카운팅 배열을 활용해서 첫 번째 단어의 각 철자를 카운팅 배열에서 더하고, 두 번째 단어의 각 철자를 카운팅 배열에서 빼면 카운팅 배열에서 0이 아닌 값들은 두 단어가 애너그램 관계에 있지 못하게 하는 값들이 된다. 카운팅 배열에서 양수인 값들은 첫 번째 단어가 두 번째 단어보다 많이 보유한 문자의 수가 되고, 음수인 값들은 두 번째 단어가 첫 번째 단어보다 많이 보유한 문자의 수(절댓값인 경우)가 되므로 카운팅 배열에서 0이 아닌 값들에 대해 절댓값들을 더하면 애너그램 관계에 있도록 만들기 위해 제거해야 하는 문자의 최소 개수가 된다.

---

2. 복잡도

접근	시간	공간
풀이	$O(N + M)$	$O(N + M)$

($N$ = s1의 길이, $M$ = s2의 길이)

---

3. 코드

풀이 [Java][C++]

import java.io.*;

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        int[] cnt = new int[26];

        String s1 = br.readLine();
        String s2 = br.readLine();

        for (char c : s1.toCharArray()) {
            cnt[c - 'a']++;
        }
        for (char c : s2.toCharArray()) {
            cnt[c - 'a']--;
        }

        int ans = 0;
        for (int x : cnt) {
            ans += Math.abs(x);
        }

        System.out.println(ans);
    }
}

#include <bits/stdc++.h>
using namespace std;

int cnt[26];

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);

    string s1, s2;
    cin >> s1 >> s2;

    for (char c : s1) cnt[c - 'a']++;
    for (char c : s2) cnt[c - 'a']--;

    int ans = 0;
    for (int x : cnt) {
        ans += abs(x);
    }

    cout << ans;
}

---