LeetCode 1347 - Minimum Number of Steps to Make Two Strings Anagram ( JavaScript )

 

안녕하세요 besforyou입니다

 

이번 글은 LeetCode 1347 - Minimum Number of Steps to Make Two Strings Anagram 풀이입니다

 

---

문제 해설

 

길이가 같은 두 개의 문자열 s 와 t 가 주어진다.

 

한 단계에서 t의 문자 한 개를 다른 문자로 바꿀 수 있다.

 

t 를 s의 anagram으로 바꾸는데 필요한 최소한의 단계를 출력하라.

 

( 한 문자열의 anagram이란같은 문자들로 이루어져있고, 문자들의 위치가 다르거나 같은 문자열을 말한다. )

 

예 : bba , bab 가 있을때 bab는 bba의 anagram이다.

 

---

문제 풀이

 

1. 문자열 s의 모든 문자에 대해 hash table에 저장한다.

2. 문자가 이미 hash table에 저장되었다면 value를 1 증가시키고

3. 문자가 저장된 적이 없다면 1을 저장한다.

 

4. 문자열 t의 모든 문자를 key로 사용해서 hash table을 참조한다.

5. hash table에 key에 대한 value가 있다면 value - 1 을 다시 저장

6. hash table에 Key에 대한 value가 없다면 문자를 바꾸어야한다는 뜻이므로 count 1 증가

7. count 출력

 

 

문자열 s = "LeetCode", t = "practice" 의 경우를 생각해보자.

[ '문자' : '개수' ] 방식으로 문자열 안의 문자와 그 문자의 개수를 표현한다면

 

s 에는 [ 'l' : 1 , 'e' : 3 , 't' : 1 , 'c' : 1, 'o' : 1 , 'd' : 1 ] 와 같은 문자가 있고

t 에는 [ 'p' : 1, 'r' : 1, 'a' : 1, 'c' : 2 , 't' : 1 , 'i' : 1, 'e' : 1 ] 와 같은 문자가 있다고 할 수 있다.

 

t의 문자를 바꾸어서 s를 만들어야한다면,

1. t에만 있는 문자의 개수와

2. s와 t에 둘 다 있지만 t에 더 많이 있는 문자가 있을때  t에 존재하는 해당 문자의 개수 - s에 존재하는 해당 문자의 개수

 

위 두 개수를 더한것이 정답이다.

 

---

코 드

 

var minSteps = function(s, t) {
    
    let hashMap = {};
    for (let letter of s) {
        if (hashMap[letter]) hashMap[letter]++;
        else hashMap[letter] = 1;
    }
    let changes = 0;
    for (let letter of t) {
        if (hashMap[letter]) hashMap[letter]--;
        else changes ++;
    }
    return changes;
};