풀이
- 인덱싱을 이용해 풀면 시간초과가 뜨지 않는다.
- 값의 범위가 0 ~ 9까지 밖에 없으므로 계수 정렬을 사용해도 공간 복잡도가 높지 않다.
- 각각의, 인덱싱을 담당하는 int 배열을 선언하여 관리하도록 한다.
코드
#include <string>
#include <vector>
using namespace std;
string solution(string X, string Y)
{
string answer = "";
int idxA[10] = { 0, };
int idxB[10] = { 0, };
for (int i = 0; i < X.size(); ++i)
{
++idxA[X[i] - '0'];
}
for (int i = 0; i < Y.size(); ++i)
{
++idxB[Y[i] - '0'];
}
for (int i = 9; i >= 0; --i)
{
while (idxA[i] > 0 && idxB[i] > 0)
{
answer += i + '0';
--idxA[i];
--idxB[i];
}
}
if (answer == "")
answer = "-1";
else if (answer[0] == '0')
answer = "0";
return answer;
}
![](https://velog.velcdn.com/images/guiltycoding/post/77ba8c9b-99f3-477c-ad74-919fad6bc673/image.PNG)