문제 설명
소문자로만 이루어진 두 문자열 S와 T가 주어집니다. S에는 어떤 문자도 두 번 이상 나타나지 않으며, S는 미리 어떤 '사용자 지정 순서'에 따라 정렬되어 있습니다. 우리가 할 일은 T의 문자들을 재배열하여 S의 정렬 순서와 일치하도록 만드는 것입니다.
좀 더 구체적으로 말하면, S에서 x가 y보다 앞에 나온다면 결과 문자열에서도 x는 y보다 앞에 위치해야 합니다. 단, S에 등장하지 않는 문자들은 결과 문자열의 어느 위치에 와도 상관없습니다.
예를 들어 S = "cba", T = "abcd"라고 가정해 보겠습니다. 이때 출력은 "cbad"가 됩니다. "a", "b", "c"는 모두 S에 등장하므로 반드시 "c", "b", "a" 순서로 배치되어야 하고, "d"는 S에 없기 때문에 어디에 놓여도 무방합니다. 따라서 "dcba", "cdba", "cbda"도 모두 유효한 답입니다.
접근 방법
이 문제는 해시 맵(빈도수 카운팅)을 활용하면 간단하게 해결할 수 있습니다. 알고리즘의 동작 과정은 다음과 같습니다.
- 결과를 담을 빈 문자열 ret을 준비합니다.
- 맵 m을 정의하고, T에 등장하는 각 문자의 빈도수를 m에 저장합니다.
- i를 0부터 S의 길이 - 1까지 반복합니다.
- x := S[i]
- j를 0부터 m[x] - 1까지 반복하며 ret에 x를 추가합니다.
- m[x] := 0으로 설정하여 해당 문자를 처리했음을 표시합니다.
- m의 각 요소 it에 대해 다음을 수행합니다.
- it의 값(빈도수)이 0보다 크다면, 그 값만큼 ret에 해당 키(문자)를 이어 붙입니다. 이는 S에 없던 문자들을 뒤에 추가하는 단계입니다.
- ret을 반환합니다.
이 방식의 시간 복잡도는 O(|S| + |T|), 공간 복잡도는 O(|T|)로 매우 효율적입니다.
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