Computer >> 컴퓨터 >  >> 프로그래밍 >> C++

C++로 두 문자열이 서로의 아나그램인지 확인하는 방법

두 문자열 'a'와 'b'가 주어졌을 때, 이 두 문자열이 서로의 아나그램(anagram)인지 확인해야 합니다. 두 문자열이 서로의 아나그램이라는 것은 한 문자열이 다른 문자열과 정확히 동일한 문자들(개수까지 포함)을 가지고 있다는 의미입니다.

예시

입력-1 −

a = anagram
b = gnarama

출력 −

True

설명 − 문자열 'gnarama'는 문자열 'anagram'과 동일한 문자들을 동일한 개수만큼 가지고 있습니다. 따라서 True를 반환합니다.

입력-2 −

a = programmer
b = mprogretmrqp

출력 −

False

설명 − 문자열 'b'가 문자열 'a'보다 더 많은 문자를 포함하고 있어 두 문자열의 길이가 다릅니다. 따라서 False를 반환합니다.

문제 해결 접근 방식

주어진 두 문자열에 대해 먼저 각 문자열의 길이를 구합니다. 길이가 다르다면 즉시 False를 반환합니다. 길이가 같다면 한 문자열의 각 문자가 다른 문자열의 문자들과 정확히 일치하는지 검사한 후, 모두 일치하면 True를 반환하고 그렇지 않으면 False를 반환합니다.

  • 두 문자열 'a'와 'b'를 입력받습니다.

  • 불리언 함수 checkAnagram(string a, string b)는 두 문자열을 인자로 받아 서로 아나그램인지 여부를 반환합니다.

  • 문자열 'a'와 'b'의 길이를 구해 서로 같은지 비교합니다. 길이가 다르면 false를 반환합니다.

  • C++ STL(표준 템플릿 라이브러리)의 unordered_map을 사용하여 문자열 'a'를 순회하면서 각 문자의 등장 횟수를 저장하는 해시 테이블을 생성합니다.

  • 동시에 문자열 'b'의 문자들은 해당 카운트에서 감소시켜, 양쪽 문자열에 공통으로 존재하는 문자는 상쇄되도록 합니다.

  • 마지막으로 맵 전체를 순회하며 카운트가 0이 아닌 문자가 남아 있는지 확인합니다. 남아 있다면 False를 반환하고, 모두 0이라면 True를 반환합니다.

구현 예제

#include<bits/stdc++.h>
using namespace std;
bool checkAnagram(string a, string b){
    int len1 = a.length();
    int len2 = b.length();
    if(len1 != len2) {
        return false;
    }
    unordered_map <char,int> mp;
    for(int i = 0; i < a.size(); i++) {
        mp[a[i]]++;   // 'a'의 문자는 증가
        mp[b[i]]--;   // 'b'의 문자는 감소
    }
    for(auto it : mp){
        if(it.second) return false; // 카운트가 남아 있으면 아나그램이 아님
    }
    return true;
}
int main(){
    string a = "anagram";
    string b = "gnarama";
    cout<< checkAnagram(a,b)<<endl;
    return 0;
}

실행 결과

위 코드를 실행하면 다음과 같은 출력이 나타납니다.

1

두 입력 문자열이 서로의 아나그램이므로 함수는 True, 즉 '1'을 반환합니다.

복잡도 분석

이 알고리즘은 두 문자열을 각각 한 번씩 순회하므로 시간 복잡도는 O(n)입니다. 여기서 n은 문자열의 길이입니다. 공간 복잡도 역시 해시 테이블에 최대 문자 종류 수만큼의 항목이 저장되므로 O(n)입니다. 정렬 기반 방식(O(n log n))보다 효율적이며, 대소문자를 구분하지 않으려면 비교 전에 모든 문자를 소문자로 변환하면 됩니다.