[Leetcode] 791. Custom Sort String

https://leetcode.com/problems/custom-sort-string/description/

Leetcode - Custom Sort String

문제 유형 : 문자열 처리, 정렬, 그리디

문제 난이도 : Medium

 

문제

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에 없는 s의 문자는 어디에도 괜찮습니다.

 

 

풀이

사용자 지정 비교 함수를 이용하여 풀 수 있다. 배열에 각 문자들의 우선순위를 order를 읽으면서 저장하고, 

그 우선순위에 맞게 정렬 함수를 쓰면 된다.

 

또는, order를 읽으면서, 정답 문자열에 (order의 문자) * (s에서의 문자개수)를 순서대로 붙이고,

마지막에 order에 없는 s의 문자를 넣으면 된다.

 

코드

C++

사용자 비교함수

class Solution {
public:
    string customSortString(string order, string s) {
        vector<int> priority(26, 1e9);
        for(int i = 0; i < order.size(); i++) {
            priority[order[i] - 'a'] = i;
        }

        sort(s.begin(), s.end(), [priority](const auto &a, const auto &b){
            return priority[a - 'a'] < priority[b - 'a'];
        });

        return s;
    }
};

 

그리디

class Solution {
public:
    string customSortString(string order, string s) {
        string ans = "";

        for(const auto &symbol : order) {
            int cnt = count(s.begin(), s.end(), symbol);

            ans += string(cnt, symbol);
        }

        for(const auto &ch : s) {
            if(order.find(ch) == string::npos) {
                ans += ch;
            }
        }

        return ans;
    }
};