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

 

#include <iostream>
#include <string>
#include <algorithm>
using namespace std;

int main() {
    int cnt=0;
    string a,b;
    int result = 0;
    cin >> a >> b;

    for(int i : a)
        {
            for(int j : b)
                {
                    if(i == j) cnt++;
                }
            if(cnt == 0) result++;
            else cnt = 0;
        }

    for(int i : b)
        {
            for(int j : a)
                {
                    if(i == j) cnt++;
                }
            if(cnt == 0) result++;
            else cnt = 0;
        }
    cout << result;

    

    return 0;
}

 

처음에는 단순히 문자열 순회하면서

같은 단어 있으면 넘어가고

같은 단어 없으면 하나 결과값을 1씩 더하는 식으로 짰는데

 

이 로직은 문자가 상대 문자열에 존재하는 지만 판단하고

몇 개 존재하는 지는 무시하게되는 문제가 있었다

#include <iostream>
#include <string>
#include <algorithm>
#include <cmath>
using namespace std;

int main() {
    string a,b;
    int result = 0;
    cin >> a >> b;
    int arr1[26] = {0};
    int arr2[26] = {0};
        
    for(char tmp : a)
        {
            arr1[tmp - 'a']++; // 숫자로 저장 
        }

    for(char tmp : b)
        {
            arr2[tmp - 'a']++; // 숫자로 저장 
        }

    for(int tmp=0; tmp<26; tmp++) // a-z까지 26개
        {
            result += abs(arr1[tmp] - arr2[tmp]);
        }
    cout << result;
    return 0;
}

 

배열 2개를 선언하여 

문자열의 각 문자가 몇 번 등장하는 지 카운트해주고

abs함수(절댓값함수)를 활용하여 몇 개를 제거해야하는 지 구한다

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

    for (char c : b)
        cnt[c - 'a']--;

    int result = 0;
    for (int i = 0; i < 26; i++)
        result += abs(cnt[i]);

 

배열을 1개만 선언하고도 풀 수 있는 방법도 있다

처음 문자열은 더하고

두번째 문자열은 빼주는게 포인트다

 

#include <iostream>
#include <vector>
using namespace std;

int main() {
    vector<int> vec1;
    vector<int> vec2;
    string a,b;
    int cnt = 0;
    cin >> a >> b;

    for(char c : a) vec1.push_back(c);
    for(char c : b) vec2.push_back(c);

    for(auto p=vec1.begin(); p<vec1.end(); p++)
        {
            for(auto p2=vec2.begin(); p2<vec2.end(); p2++)
                {
                    if(*p == *p2)
                    {
                        cnt++;
                        vec2.erase(p2);
                        break;
                    }
                }
        }

    cout << vec1.size() - cnt + vec2.size();
    return 0;
}

 

이중 반복문을 사용한 풀이도 있다

iterator를 사용하여 벡터에 접근하고

값이 같으면 그 위치를 삭제해주는 방식이다

 

양 쪽 다 삭제해서 두 벡터의 size를 더하면 되지않을까 생각해봤는데

erase하게되면 다음 위치의 iterator가 반환되고

break되고 나왔을 때 한 번 더 1이 더해져서

두 칸을 점프하게되는 문제가 발생한다

 

그래서 한 쪽만 없애고 cnt를 카운트해줘서

다른 한쪽 size에서 cnt를 빼주는 방식으로 처리했다