[LeetCode] 791. Custom Sort String

문제

You are given two strings order and s. All the characters of order are unique and were sorted in some custom order previously. Permute the characters of s so that they match the order that order was sorted. More specifically, if a character x occurs before a character y in order, then x should occur before y in the permuted string. Return any permutation of s that satisfies this property.

두 개의 문자열, 'order'와 's'가 주어집니다. 'order'의 모든 문자는 고유하며 이전에 어떤 사용자 정의 순서로 정렬되었습니다. 's'의 문자를 순서대로 재배열하여 'order'가 정렬된 순서와 일치하도록 합니다. 구체적으로, 'order'에서 문자 x가 문자 y보다 앞에 오면, 재배열된 문자열에서도 x가 y보다 앞에 와야 합니다. 이 조건을 만족하는 's'의 어떤 순열이든 반환하세요.

 

풀이

1. Hashmap

알고리즘

1. s의 각 문자를 순회하며, char_count 해시맵에 해당 문자의 출현 횟수를 저장합니다.

2. order의 각 문자를 순회하며 해당 문자가 char_count 해시맵에 존재하는 경우 출현횟수 만큼 answer에 추가하고 char_count에서 해당 문자를 삭제시킵니다.

3. 나머지 char_count에 있는 문자를 answer에 추가합니다.

class Solution(object):
    def customSortString(self, order, s):
        answer = ""
        char_count = {}
        for char in s:
            char_count[char] = char_count.get(char, 0) + 1
        
        for order_ch in order:
            if(order_ch in char_count):
                answer += order_ch * char_count[order_ch]
                del char_count[order_ch]

        for char in char_count:
            answer += char * char_count[char]

        return answer

 

복잡도

• 시간 복잡도: O(n + m) 
• 공간 복잡도: O(n)