791. Custom Sort String (Hash Table, String, Sorting)

링크 - https://leetcode.com/problems/custom-sort-string/description/?envType=company&envId=facebook&favoriteSlug=facebook-thirty-days

난이도 - Medium

Intuition

우리는 O(n)의 시간복잡도로 이 문제를 풀 수있다. 먼저 Counter를 사용해 주어진 s의 frequency를 계산한다. 그 다음, order를 for문으로 돌면서, 나온 글자들이 counter에 있는지 확인하고, 있으면 counter의 frequency만큼 ans에 더한다. 그리고 counter에서 나온 글자를 지운다. 그러면 for문이 끝나고 counter에 남아있는 글자들이 있을 것이다. 그 글자들은 마지막에 더해주면 된다.

Code

class Solution:
    def customSortString(self, order: str, s: str) -> str:
        counter = Counter(s)
        ans = ""

        for c in order:
            if c in counter:
                ans += c * counter[c]
                del counter[c]

        for k, v in counter.items():
            ans += k*v

        return ans

Complexity

Time Complexity: O(n) Counter에 n, ans를 만드는데 n이 소요된다.

Space Complexity: O(n) counter가 최대 n개의 아이템을 가지고 있다.