[LeetCode] 1347. Minimum Number of Steps to Make Two Strings Anagram

https://leetcode.com/problems/minimum-number-of-steps-to-make-two-strings-anagram/description/

Minimum Number of Steps to Make Two Strings Anagram - LeetCode

leetcode - Minimum Number of Steps to Make Two Strings Anagram

문제 유형 : 해시, 문자열처리

문제 난이도 : Medium

 

 

문제

You are given two strings of the same length s and t. In one step you can choose any character of t and replace it with another character.

Return the minimum number of steps to make t an anagram of s.

An Anagram of a string is a string that contains the same characters with a different (or the same) ordering.

 

당신은 두 개의 문자열 s와 t를 받습니다.

당신은 t의 한 문자를 정해서 다른 문자로 바꿀 수 있습니다.

t를 바꿔서 s의 애너그램이 되는 최소 횟수를 반환하시오.

애너그램은 한 문자열에서 같은 문자들로 재배열하여 나오는 새로운 문자열을 의미합니다.

 

 

풀이

char, int의 map을 만들어서 s의 문자들의 개수를 모아놓는다.

 

다음, t를 한 번 순회하면서 map의 각 문자의 개수를 뺀다.

이러면 map[문자] > 0인 문자는 s에 있고, t에는 없는 문자이고, map[문자] < 0인 문자는 s에없고, t에 있는 문자란 뜻이다.

 

map에 있는 각 쌍에서 양수들만 더하면 최소 회수가 나온다.

또는 양수와 음수 절대값을 모두 더하여 2로 나눔으로써 구할 수 있다.

 

 

코드

C++

static const int __ = [](){
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    return 0;
}();

class Solution {
public:
    int minSteps(string s, string t) {
        unordered_map<char, int> mp;
        for(const auto &ch : s) {
            mp[ch]++;
        }

        for(const auto &ch : t) {
            mp[ch]--;
        }

        int sum = 0;
        for(const auto &m : mp) {
            sum += abs(m.second);
        }
        return sum/2;
    }
};

 

hash table

<컴퓨터>해시표(~表)