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

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

프로그래머스

 

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


int solution(vector<int> A, vector<int> B)
{
    int sum=0;
    sort(A.begin(),A.end());
    sort(B.begin(),B.end(),greater<>());
   
        for(int i=0;i<A.size();i++)
        {
            sum+=A[i]*B[i];

        }
    
    return sum;
}

 

두 벡터가 주어졌을 때 원소의 순서를 바꿔서 최소값이 되는 경우를 찾는 문제이다.

처음 봤을 때, 직관적으로 제일 큰 수랑 제일 작은 수를 곱하는 경우가 최소일 거라는 느낌이 왔는데

암산으로 예제케이스를 해보니 답이랑 틀려서 다른 방법을 고민했었다.

 

하지만 나의 암산실수였고 처음 생각한 것이 답이었다. 

 

다른방법을 생각하며 이중포문으로 일일이 계산하는 방법을 떠올렸는데 시간초과가 발생했다. 

질문하기로 다른코드를 봤을 때,

#include<algorithm>

vector<int> a;

void func()
{
	while(next_permutation(a.begin(),a.end()))
    {}
}

이 함수를 알게되었다. 

 

순열을 구해주는 라이브러리 함수인데, a벡터의 순서를 변경해서 리턴해주며 함수의 리턴값은 bool 값으로 더 이상의 순열이 없을 경우 false를 리턴해서 위와 같이 사용이 가능하다.

 

하지만 이 방법도 결국 시간초과가 발생했다.

 

다음은 for문을 좀 더 간편하게 한줄로 처리할 수 있는 내적관련 라이브러리 함수이다.

#include<numeric>

void func()
{
	vector<int>a;
    vector<int>b;
    
    inner_product(a.begin(),a.end(),b.begin());
}

다음과 같이 사용하면 a의 시작~끝까지 원소에 대해 b의 원소를 처음부터 시작해 내적한다.