C++의 사용자 정의 정렬 문자열

S와 T 두 개의 문자열이 소문자로 구성되어 있다고 가정합니다. S에서는 문자가 두 번 이상 나오지 않습니다. S는 이전에 일부 사용자 지정 순서로 정렬되었습니다. S가 정렬된 순서와 일치하도록 T의 문자를 치환해야 합니다. 보다 구체적으로, S에서 x가 y보다 먼저 발생하면 반환된 문자열에서 x가 y보다 먼저 발생합니다.

따라서 S ="cba"이고 T ="abcd"이면 출력은 "cbad"가 됩니다. 여기서 "a", "b", "c"는 S에 나타나므로 "a", "b", "c"의 순서는 "c", "b", "a"여야 합니다. "d"는 S에 나타나지 않으므로 T의 모든 위치에 있을 수 있습니다. "dcba", "cdba", "cbda"도 유효한 출력입니다.

이 문제를 해결하기 위해 다음 단계를 따릅니다. −

• ret를 빈 문자열로 설정

• 맵 m을 정의하고 T에 있는 각 문자의 빈도를 m

  에 저장합니다.

• 범위 0에서 S – 1까지의 i에 대해

  • x :=S[i]

  • 범위 0에서 m[x] – 1까지의 j에 대해

    • 렛 :=렛 + x

  • m[x] :=0

• 각 쌍에 대해 m −

  • 값이 0보다 크면

    • 범위 0에서 그것의 값 – 1에 있는 i에 대해

      • ret :=ret 연결 키

• 리턴 렛

예시(C++)

더 나은 이해를 위해 다음 구현을 살펴보겠습니다. −

#include <bits/stdc++.h>
using namespace std;
class Solution {
   public:
   string customSortString(string S, string T) {
      string ret = "";
      unordered_map <char, int> m;
      for(int i = 0; i < T.size(); i++){
         m[T[i]]++;
      }
      for(int i = 0; i < S.size(); i++){
         char x = S[i];
         for(int j = 0; j < m[x]; j++){
            ret += x;
         }
         m[x] = 0;
      }
      unordered_map <char, int> :: iterator it = m.begin();
      while(it != m.end()){
         if(it->second > 0){
            for(int i = 0; i < it->second; i++)ret += it->first;
         }
         it++;
      }
      return ret;
   }
};
main(){
   Solution ob;
   cout << (ob.customSortString("cba", "abcd"));
}

입력

"cba"
"abcd"

출력

cbad