programmers 최솟값 만들기

programmers

level2 최솟값 만들기

문제 설명

길이가 같고 자연수로 이루어진 두 배열이 주어지고 두 배열의 값들 중에서 중복 없이 하나씩 뽑아 곱셈을 한다. 이를 배열에 더이상 뽑을 숫자가 없을 때까지 진행하고 곱의 결과값들의 합의 최솟값을 구하는 문제이다.

#include <vector>
#include <algorithm>

using namespace std;

bool descend(int j, int k){
    return j>k;
}

int solution(vector<int> A, vector<int> B)
{
    int answer = 0;

    sort(A.begin(), A.end());
    sort(B.begin(), B.end(), descend);

    for(size_t i=0; i < A.size(); ++i) answer+=A[i]*B[i];

    return answer;
}

해결 과정

처음에 보고 직관적으로 모든 경우의 수를 탐색해야하나 생각했지만 배열의 크기가 1000개인 것을 보고 안 된다는 것을 깨달았다. 곱셈의 특성을 고려하여 선택할 수 있는 가장 큰 숫자와 가장 작은 숫자를 선택하면 최솟값을 얻을 수 있겠다라고 생각이 들었다. 다음에 해결해야 할 것은 정렬이었다. algorithm 라이브러리에 sort() 함수를 사용하려고 했고, 해당 함수는 오름차순 혹은 사용자 생성 함수를 이용해서 정렬해준다는 것을 알고 있었다. 따라서 앞의 값보다 뒤의 값이 더 작아야 True를 반환하는 함수를 이용했다.
sort()함수의 시간복잡도가 평균적으로 O(nlogn)으로 sort()를 이용하니 무난하게 통과할 수 있었다. 다른 사람의 풀이를 보니 새로 함수를 생성하는 것보다 더 간단한 방법이 있어 밑에 기술한다.

• greater 사용하는 방법

  sort(B.begin(), B.end(), greater<int>());

• lambda 표현식 사용

  sort(B.begin(), B.end(), [](int a, int b) { return a > b; });

• reverse 함수 사용

  sort(B.begin(), B.end()); reverse(B.begin(), B.end());

• rbegin(), rend() 사용

  sort(B.rbegin(), B.rend());

다양한 정렬방법을 배울 수 있었다.