숫자 짝꿍

1차 풀이

정답이긴 한데 일부 예시에서 너무 과도한 풀이시간이 발생했다. 예시 11~15번에서 다른 사람들의 10~40배 더 되는 시간이 걸렸다.

#include <string>
#include <vector>
#include <algorithm>
#include <iostream>

using namespace std;

string solution(string X, string Y) {
    string answer = ""; 
    int i, j, temp = 0;
    bool zero = true;
    
    //이중 for문 하면 300만 * 300만이 되는데...
    sort(X.begin(), X.end(), greater<>());//X의 내림차순 정렬
    sort(Y.begin(), Y.end(), greater<>());//Y의 내림차순 정렬
    //cout << X << " " << Y << "\n";
    
    for(i = 0; i < X.length(); i++){
        for(j = temp; j < Y.length(); j++){
            if(X[i] == Y[j]){
                temp = j + 1;
                answer += X[i];
                //cout << answer << "\n";
                break;
            }
        }
    }
    if(answer == ""){
        answer = "-1";
    }
    else if(answer[0] == '0'){
        answer = "0";
    }
    
    return answer;
}

2차 풀이

반복문을 하나로 줄여 시간을 크게 줄일 수 있다.
이때 최종 결과 확인 부분에서 answer에 =로 단순 재할당하는 것과 clear()로 메모리 초기화 후 할당의 차이를 알아봤는데 이 정도 데이터 크기에서는 크게 의미가 없는거 같다.

또한 empty()는 문자열 타입에서도 사용함을 배웠다.

#include <string>
#include <vector>
#include <algorithm>
#include <iostream>

using namespace std;

string solution(string X, string Y) {
    string answer = "";
    int X_length = X.length(), Y_length = Y.length();
    int X_i = 0, Y_i = 0;
    
    //정렬은 동일
    sort(X.begin(), X.end(), greater<>());//X의 내림차순 정렬
    sort(Y.begin(), Y.end(), greater<>());//Y의 내림차순 정렬
    
    while(X_i != X_length && Y_i != Y_length){
        if(X[X_i] == Y[Y_i]){
            answer += X[X_i];
            X_i++;
            Y_i++;
        }
        else if(X[X_i] < Y[Y_i]){//내림차순 정렬을 했는데, X가 Y보다 작다면?
            //X보다 작은 Y가 나올때까지 Y 증가
            //이미 정렬을 다 한 상태고, X와 Y가 겹치는 수가 없다는 의미
            Y_i++;
        }
        else{//X[X_i] >= Y[Y_i]
            //X가 Y와 겹치는 수가 없고 X가 Y보다 큰 상황
            X_i++;
        }
    }
    
    /*
    if(answer == ""){
        answer = "-1";
    }
    else if(answer[0] == '0'){
        answer = "0";
    }
    */
    
    if(answer.empty()){
        answer = "-1";
    }
    else if(answer[0] == '0'){
        answer.clear();
        answer = "0";
    }
    
    return answer;
}