[LeetCode] 791. Custom Sort String

문제 출처: https://leetcode.com/problems/custom-sort-string/

Custom Sort String - LeetCode

 

문제

order와 str은 소문자로 이루어진 문자열이다. order에서 문자는 반복되어 나타나지 않는다.

 

order는 사전에 사용자가 정의한 순서대로 정렬되어 있다. str의 순열을 얻고자 하는데, 이 순열은 order가 정렬된 순서와 일치해야 한다. 더 자세하게 말하자면 만약 order에서 x가 y보다 먼저 등장했다면, 반환된 문자열에서도 x는 y전에 등장해야 한다.

 

이러한 속성을 만족하는 문자열 str의 순열을 반환하라.

 

예제

Input: order = "cba", str = "abcd"
Output: "cbad"

Explanation: 
"a", "b", "c" appear in order, so the order of "a", "b", "c" should be "c", "b", and "a". 
Since "d" does not appear in order, it can be at any position in the returned string. "dcba", "cdba", "cbda" are also valid outputs.

 

풀이

str을 order의 순서대로 정렬하기 위해서 일반적으로 알고 있는 O(nlogn)의 정렬 기법을 사용할 수 있다.

 

정렬 알고리즘을 사용하기 위해서는 문자 간의 비교가 가능해야 하므로, order의 문자가 등장하는 순서대로 값을 부여함으로써 이를 가능하게 할 수 있다.

order = 'cba'

char:    c     b    a
val:     1     2    3

위의 예와 같이 order의 등장 순서대로 값을 부여하고, 이 값을 기준으로 str을 정렬함으로써 원하는 답을 얻을 수 있다, 만약 str에 order에 등장하지 않는 문자가 존재한다면, 0 또는 26 값을 부여하여 정렬에 사용하면 된다.

var customSortString = function(order, str) {
    const customOrder = new Array(26).fill(27);

    const codeA = 'a'.charCodeAt(0);
    for (let i = 0; i < order.length; i++) {
        const ascii = order[i].charCodeAt(0)

        customOrder[ascii - codeA] = i + 1;
    }

    const strList = str.split('');
    const ansList = strList.sort((a, b) => {
        return customOrder[a.charCodeAt(0) - codeA] - customOrder[b.charCodeAt(0) - codeA]
    })

    return ansList.join('');
};

O(n + k) 시간복잡도로 문제를 해결할 수 있는데, 정렬 알고리즘 중 특별한 경우에 사용할 수 있는 Counting Sort(계수 정렬) 를 사용하는 것이다. 계수정렬은 특정 범위에 있는 수를 정렬할 때 사용하는 알고리즘으로 정렬을 위한 추가 공간이 필요한 알고리즘이다.

 

계수정렬을 이용하기 위해서 가장 먼저 할 일은 str에 등장하는 문자들의 빈도수를 세는 것이다.

str = 'abcd`

char | a | b | c | d |
freq | 1 | 1 | 1 | 1 |

이제, order를 순차적으로 순회하면서, order의 문자가 str에서 등장했는지 체크하고, 등장했다면 등장한 빈도만큼 결과에 추가해주는 방식으로 정렬된 문자열을 만들어 간다.

str = 'abbcd', order = 'cba'

- ans = ''
- freq_map =>    char | a | b | c | d |
                freq | 1 | 2 | 1 | 1 | 

1) order[0] = 'c' :

    freq_map['c'] = 1
    ans += 'c' (ans = 'c')

    freq_map => char | a | b | d |
                freq | 1 | 1 | 1 | 


2) order[1] = 'b' :

    freq_map['b'] = 2
    ans += 'bb' (ans = 'cbb')

    freq_map => char | a | d |
                freq | 1 | 1 | 


3) order[2] = 'a' :

    freq_map['a'] = 1
    ans += 'a' (ans = 'cbba')

    freq_map => char | d |
                freq | 1 | 


4) order를 순회하고도 남은 문자가 있다면, 모두 ans에 추가

    freq_map => char | d |
                freq | 1 | 

    ans += 'd' (ans = 'cbbad')

위의 과정을 코드로 작성하면 다음과 같다.

var customSortString = function(order, str) {
    let ans = '';

    const charMap = new Map();
    for (let i = 0; i < str.length; i++) {
        if (!charMap.has(str[i])) { charMap.set(str[i], 0); }
        charMap.set(str[i], charMap.get(str[i]) + 1);
    }

    // order에 정의된 문자
    for (let i = 0; i < order.length; i++) {
        if (!charMap.has(order[i])) { continue; }

        ans += order[i].repeat(charMap.get(order[i]));
        charMap.delete(order[i]);
    }

    // order에 정의되지 않은 나머지 문자
    for (let [char, freq] of charMap.entries()) {
        ans += char.repeat(freq);
    }

    return ans;
};

 

Github: 791.js

opwe37/Algorithm-Study