[Lv 1] 숫자 짝꿍

https://school.programmers.co.kr/learn/courses/30/lessons/131128

프로그래머스

 

이 문제는 문자열 조작을 통해 해결할 수 있다.

주어진 문자열은 숫자로 이루어져 있으며, 같은 숫자를 찾아 가장 큰 값을 만들어 반환해야한다.

X와 Y의 최대 크기는 3,000,000이므로 이중 반복을 통해 찾게 된다면 시간 초과가 발생할 수 있다.

 

따라서 한번의 반복으로 2개의 문자열에 존재하는 같은 문자 쌍을 찾아야한다.

이를 위해 X와 Y에 존재하는 문자를 작은 값 순서로 정렬을 진행한다.

이러면 각 문자열의 마지막 값은 존재하는 문자 중 가장 큰 값이 된다.

 

가장 큰 값부터 쌍을 찾을 때 현재 값이 같다면 배열에 삽입하고 문자를 제거한다.

다른 경우 2개의 문자 중 가장 큰 값을 가진 문자열의 마지막 문자를 제거한다.

이후 다시 비교의 과정을 거치고 2개의 문자열 중 빈 문자열이 생기는 경우 반복을 멈춘다.

 

배열이 비어있는 경우 쌍을 찾지 못한 경우이기 때문에 -1을 반환한다.

정렬 후 가장 마지막 값이 0인 경우는 0으로만 값을 만들 수 있으므로 0을 반환한다.

2가지 경우에 해당하지 않으면 마지막 요소부터 answer 문자열에 값을 채우고 반환한다.

 

#include <string>
#include <vector>
#include <algorithm>
using namespace std;

string solution(string X, string Y) {
    string answer = "";
    vector<char> v;

    sort(X.begin(), X.end());
    sort(Y.begin(), Y.end());

    char dx, dy;
    while(!X.empty()&&!Y.empty()){
        dx = X.back();
        dy = Y.back();
        
        if(dx == dy){
            v.push_back(dx);
            X.pop_back();
            Y.pop_back();
        }
        else{
            if(dx > dy)
                X.pop_back();
            else
                Y.pop_back();
        }
    }
    if(v.empty())
        return "-1";
    
    sort(v.begin(),v.end());
    if(v[v.size() - 1] == '0')
        return "0";
    
    for(int i = v.size() - 1;i>=0;i--)
        answer += v[i];
    
    return answer;
}