[2024] day 72. Leetcode 791. Custom Sort String

2024년부터 새롭게 다시 시작하는 코딩테스트

2024년 3월 11일 (월)
Leetcode daily problem

Leetcode 791. Custom Sort String

https://leetcode.com/problems/custom-sort-string/?envType=daily-question&envId=2024-03-11

Problem

두 개의 문자 order, s가 주어집니다.
order 문자는 사용자 정의대로 정렬되어 있습니다.
문자 s에 있는 문자열은 문자 order와 매치 했을 때 문자 order에 있는 정렬된 정의를 따르도록 문자를 치환해야합니다.
이 속성을 만족하는 s의 순열을 반합니다.

즉,

예시 1에서 order = 'cba', s='abcd' 일 경우
s의 'abcd'의 문자열 'abc'는 'cba'로 정렬되어 있으므로
s 문자열은 'cba'로 정렬하고 나머지 d는 사용자정의 정렬이 없으므로 정렬된 문자열에 그대로 붙여 최종 출력은 'cbad'가 됩니다.

"d"는 순서대로 나타나지 않으므로 반환된 문자열의 어느 위치에나 있을 수 있어서, "dcba", "cdba", "cbda"도 유효한 답입니다.

Solution

array

최종 문자열은 s를 재정렬해서 반환하는 것이므로, 문자 s를 기준으로 문자열의 빈도에 대한 맵을 하나 생성한다.

그 후 order 문자열을 기준으로 s를 재정렬해야하므로,
order의 문자열을 하나씩 탐색해가면서 만들어낸 s 문자열에 대한 빈도수를 담은 맵에서의 문자열의 유무를 파악한다. order에 s를 구성하는 문자열이 있다면, 빈도수만큼 반환할 문자열에 붙이고, s 문자열 빈도 맵에서의 해당 문자열을 삭제한다.

order를 한번 다 돌고 나서 남은 s 문자열 빈도 맵에서 남은 문자를 빈도수에 따라 붙여주고 최종 문자열로 반환하면 되는 문제이다.

Code

class Solution:
    def customSortString(self, order: str, s: str) -> str:
        charDict = {}
        for c in s:
            charDict[c] = charDict.get(c, 0) +1
        
        result = ''
        for c in order:
            if c in charDict:
                result += c * charDict[c]
                del charDict[c]
        
        for char, cnt in charDict.items():
            result += char * cnt

        return result

Complexicity

시간 복잡도

문자열 s의 길이를 탐색하면서 빈도를 파악하므로 시간복잡도는 O(n) 이 소요된다. 그 후에 order 문자열도 한번 탐색하므로 O(m) 이다.
마지막 남은 문자들을 처리할 때 또 한번 탐색하게 되는데 최악의 경우 O(n)이 소요될 수 있다. 최종 시간복잡도는 O(n+m) 이다.
n : s의 문자열 사이즈 , m :order 문자열 사이즈

공간 복잡도

charDict라는 해시 맵을 사용하여 문자의 발생 빈도를 저장하므로, O(n)의 공간복잡도를 가진다.