[프로그래머스 1단계] 알고리즘 17. 최솟값 만들기

문제 출처는 프로그래머스 알고리즘 연습 에서 볼 수 있습니다!(https://programmers.co.kr/learn/challenges)

알고리즘 17. 최솟값 만들기[2단계]

자연수로 이루어진 길이가 같은 수열 A,B가 있습니다. 최솟값 만들기는 A, B에서 각각 한 개의 숫자를 뽑아 두 수를 곱한 값을 누적하여 더합니다. 이러한 과정을 수열의 길이만큼 반복하여 최종적으로 누적된 값이 최소가 되도록 만드는 것이 목표입니다.

예를 들어 A = [1, 2] , B = [3, 4] 라면

1. A에서 1, B에서 4를 뽑아 곱하여 더합니다.
2. A에서 2, B에서 3을 뽑아 곱하여 더합니다.

수열의 길이만큼 반복하여 최솟값 10을 얻을 수 있으며, 이 10이 최솟값이 됩니다. 수열 A,B가 주어질 때, 최솟값을 반환해주는 getMinSum 함수를 완성하세요.

#include<iostream>

#include<vector>

using namespace std;

int getMinSum(vector<int> A, vector<int> B)

{

    int answer = 0;

    return answer;

}

int main()

{

    vector<int> tA{1,2}, tB{3,4};

    //아래는 테스트 출력을 위한 코드입니다.

    cout<<getMinSum(tA,tB);

}

풀이 : 

자 설레는 마음으로 오랜만에 C++로 풀어보았다. 문제의 핵심은 두 벡터에서 한 개씩 뽑아 곱한 값들의 합을 최소로 어떻게 만드느냐!이다. 이것의 답은 한 벡터는 최소값 순으로 다른 한 벡터는 최대값 순으로 원소를 뽑은 후에 곱해줘서 합하면 된다. 그렇게 하기 위해서 나는 코드의 흐름 순서를 다음과 같이 정했다.

1. A를 오름차순으로 정렬한다.(최솟값을 순서대로 뽑는 벡터)

2. B를 내림차순으로 정렬한다.(최댓값을 순서대로 뽑는 벡터)

3. A,B를 동시에 순회하여 얻은 값들을 곱해준 후 answer에 누적

코드는 다음과 같다.

#include<algorithm>

bool AscendingFunc(int i1, int i2)

{

   return i1 < i2;

}

bool DescendingFunc(int i1, int i2)

{

   return i1 > i2;

}

int getMinSum(vector<int> A, vector<int> B)

{

    int answer = 0;

  std::sort(A.begin(), A.end(), AscendingFunc); //1. A 오름차순 정렬

std::sort(B.begin(), B.end(), DescendingFunc); //2. B 내림차순 정렬

for(int i=0; i<A.size(); i++)

{

 answer += (A[i] * B[i]); //3. A, B 순회하면서 곱해준 값 누적

}

    return answer;

}

코드에서 설명할 것이 몇가지 있다. 먼저 sort함수는 컨테이너를 정렬시키는 c++ algorithm 라이브러리 안에 정의 되어 있는 함수이다. sort는 여러개 오버로딩을 가지고 있는데 기본적으로 쓰는 원형은 다음과 같다.

std::sort(A.begin(), A.end());

이러면 A의 시작부터 끝까지 돌아서 A를 오름차순(Ascending order)으로 정렬한다. 만약 정렬 기준을 바꾸고 싶다면 위처럼 정렬 기준이 되는 함수(compare함수)를 보내주거나 클래스를 보내주어야 한다. 주의할 점은 vector<T> 일 때 compare 함수 인자는 (T t1, T t2)가 되어야 함을 명심하자. 코드에서는 오름차순과 내림차순을 명시하기 위해 위처럼 적었으나 람다식을 보내줘도 상관없다. 다음으로 벡터의 순회 방법에 대해서 알아보자. 벡터 순회는 다음의 3가지 방식이 있다. 코드와 함께 알아보자.

1. iterator 순회

vector<int>::iterator iter=v.begin(); // 벡터 반복자 시작지점

for (iter = v.begin(); iter != v.end(); ++iter){

//순회 코드

}

먼저 벡터 v의 begin()함수는 vector의 시작점을 가리키는 이터레이터를 반환한다는 것을 알면 이터레이터 순회는 금방 이해가 갈 것이다. 값을 접근할 때는 *iter 로 접근한다.(이터레이터 자체가 포인터다!)

2. 인덱스 순회

for(int i=0; i<v.size(); i++)

{

 //순회 코드

}

아마 제일 익숙한 순회방식일 듯 싶다. 원소를 v[i]로 접근한다. 문제처럼 길이가 같은 벡터를 여러개를 동시에 순회할때 유용하다.

3. foreach 형식 순회

for(int elem : v)

{

//순회 코드

}

c++ 역시 foreach 구문을 지원한다. 여기서 elem은 v를 순회하면서 원소들을 순서대로 접근한다. 2번에서 v[i]가 elem이라고 생각하면 된다

코드에서는 2번 인덱스 순회를 하였다. 이로써 이번 문제에 대한 설명은 끝났다! 우선 나에게 축하의 말을 전한다. 1단계의 25문제를 다 풀고 드디어  드디어 2단계다 ㅠㅠ(1단계 9문제는 블로그에 올리지 않았습니다.)