프로그래머스 - 최솟값 만들기

프로그래머스 - 최솟값 만들기

처음에 순열을 만들어서 풀었다가 실제로 제출하니까 시간초과가 나서 틀렸다.
주어진 두 문자열의 길이가 1000 이하라서 괜찮을 줄 알았는데, 실패해서 다른 방법을 생각했다.

생각을 해보니 A 문자열은 오름차순으로 정렬하고, B 문자열은 내림차순으로 정렬한 뒤, A[i] * B[i]를 다 더해주면 최솟값이 되는 것을 파악했다.

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

using namespace std;

bool comp(const int &a, const int &b)
{
    return a > b;
}
int solution(vector<int> A, vector<int> B)
{
    int answer = 0;
    int size = A.size();
    
    sort(A.begin(), A.end());
    sort(B.begin(), B.end(), comp);
    
    for(int i=0;i<size;i++) 
        answer += A[i] * B[i];
    
    return answer;
}