[백준][C++] 1919번 애너그램 만들기

애너그램 만들기

문제 링크

애너그램 만들기

분석

첫째 줄과 둘째 줄에 영어 단어 소문자로 이루어진 문자열이 주어집니다.

두 문자열이 애너그램이 될 수 있도록 제거해야 하는 최소 개수의 문자 수를 구하는 문제입니다.

애너그램은 단어의 철자 순서를 뒤바꾸어 같아질 수 있을 때 애너그램 관계에 있다고 합니다.
예를 들어 occurs라는 영어 단어와 succor은 서로 애너그램 관계에 있는데, occurs의 각 문자들의 순서를 잘 바꾸면 succor 이 되기 때문입니다.

두 문자열이 다르게 가지고 있는 문자를 제거해야하기 때문에 제거하려는 문자의 수를 구하면 쉽게 문제를 풀 수 있습니다.

풀이

#include <iostream>
#include <string>
#include <cmath>

using namespace std;

int main()
{
    string inputStringA;
    string inputStringB;

    cin >> inputStringA >> inputStringB;

    int AlphabetCountA[26] = {};
    int AlphabetCountB[26] = {};

	// 첫째 줄의 문자열이 가진 문자의 개수를 구한다.
    for (int i = 0; i < inputStringA.length(); ++i)
    {
        int AlphabetIndex = inputStringA[i] - 'a';
        ++AlphabetCountA[AlphabetIndex];
    }

	// 둘째 줄의 문자열이 가진 문자의 개수를 구한다.
    for (int i = 0; i < inputStringB.length(); ++i)
    {
        int AlphabetIndex = inputStringB[i] - 'a';
        ++AlphabetCountB[AlphabetIndex];
    }
	
    int result = 0;
    
    // 두 문자열이 서로 다르게 가지고 있는 문자의 개수를 구한다.
    for (int i = 0; i < 26; ++i)
    {
        result += abs(AlphabetCountA[i] - AlphabetCountB[i]);
    }

    cout << result;

    return 0;
}

성능 요약

시간 복잡도는 $O(l)$입니다.

• 문자열의 문자 수를 구하는 반복문 $O(l)$
  • $l$은 문자열의 최대 길이를 의미합니다.
• 필요한 문자 수를 구하는 반복문 $O(26) \approx O(1)$
• $O(l) + O(l) + O(1)$

공간 복잡도는 고정된 크기의 상수 공간을 사용하기 때문에 $O(1)$입니다.

메모리: 2024 KB

시간: 0 ms