[프로그래머스/Level 2] 최솟값 만들기 (C++)

programmers.co.kr/learn/courses/30/lessons/12941

코딩테스트 연습 - 최솟값 만들기

 

입력값의 범위가 1000 이하의 자연수라서 next_permutation을 이용하여 한 배열의 순열을 구하고, 이를 통해 최소값을 구하려고 했는데 이상하게 시간 초과가 발생한다. (O(N^2)로도 풀려야한다고 생각했는데... 접근이 잘못됐나,, 이유를 모르겠다.)

 

그래서 다른 풀이는 O(N)으로 해결할 수 있는 방법으로, 각 곱을 합한 최소값은 최대값 x 최소값으로 이루어진 곱들을 합하는 것이였다. A는 오름차순, B는 내림차순으로 정렬한 후 곱의 합을 구하였다.

 

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

int solution(vector<int> A, vector<int> B) {
    int answer = 0;
    sort(A.begin(), A.end()); // 오름차순
    sort(B.begin(), B.end(), greater<>()); // 내림차순
    
    for(int i = 0; i < A.size(); i++) {
        answer += A[i] * B[i];
    }

    return answer;
}