[릿코드 1347] Minimum Number of Steps to Make Two Strings Anagram (파이썬/python)

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

Minimum Number of Steps to Make Two Strings Anagram - LeetCode

 

 

단순히 S 와 T 의 문자열을 비교해서 개수를 세주면 되는 문제

처음에 반복문으로 문제를 풀었는데 시간복잡도 이슈가 있어서

딕셔너리를 사용하여 문제를 풀었다.

 

 

 

# 내가 푼 풀이

class Solution:
    def minSteps(self, s: str, t: str) -> int:
        s_dic = {}
        t_dic = {}

        s_list = []

        result = 0

        for sub_s in s:
            if sub_s in s_dic:
                s_dic[sub_s] += 1
            else:
                s_dic[sub_s] = 1
                s_list.append(sub_s)

        for sub_t in t:
            if sub_t in t_dic:
                t_dic[sub_t] += 1
            else:
                t_dic[sub_t] = 1

        print(s_dic, t_dic, s_list)

        for s_element in s_list:
            if s_element in t_dic:
                difference = t_dic[s_element] - s_dic[s_element]

                if difference < 0:
                    result += t_dic[s_element]
                else:
                    result += s_dic[s_element]

        return len(s) - result

 

 

# 다른분의 정답에서 참고한 풀이 

class Solution:
    def minSteps(self, s: str, t: str) -> int:
        s_dic = {}

        result = 0

        for sub_s in s:
            s_dic[sub_s] = s_dic.get(sub_s, 0) + 1

        for sub_t in t:
            if sub_t in s_dic:
                s_dic[sub_t] -= 1

                if s_dic[sub_t] < 0:
                    result += 1

            else:
                result += 1

        return result

 

 

# 맨 처음 시도한 딕셔너리를 안쓴 반복문 풀이(실패)

class Solution:
    def minSteps(self, s: str, t: str) -> int:
        t_idx_list = []
        collect_cnt = 0

        for s_idx in range(len(s)):
            for t_idx in range(len(t)):
                if s[s_idx] == t[t_idx]:
                    if t_idx not in t_idx_list:
                        print(s_idx, t_idx, t_idx_list)
                        t_idx_list.append(t_idx)
                        collect_cnt += 1
                        break

        return len(s) - collect_cnt