[알고리즘_Programmers] 8주차 2번 문제 및 풀이

이번 포스팅에서는 "최솟값 만들기"라는 문제에 대해서 풀이를 진행해보려 한다.

 

이번 문제도 지난 1번 문제와 마찬가지로 크게 어려운 문제는 아니었다.

 

우선 문제는 다음과 같다.

 

<문제>

 

<1. 나의 풀이>

 

• 배열 A와 B가 주어질 때 누적된 합이 최소가 되도록 하려면, "(배열 A의 최솟값1 * 배열 B의 최댓값1) + (배열 A의 최솟값2 * 배열 B의 최댓값2) + ... " 이런 식으로 누적합을 구해주면 된다.
  • 여기서 최솟값1은 모든 값들 중에서 최솟값을 의미하고, 최솟값2는 최솟값1을 제외한 모든 값들 중에서 최솟값을 의미한다. 최댓값도 동일하게 적용된다.

• 따라서 먼저 배열 A를 오름차순 정렬해주고, 배열 B를 내림차순 정렬해주었다. (동일한 index를 갖는 값들끼리 곱해주기 위해서)
• 그 다음, 배열 A와 B에서 동일한 index를 갖는 값들끼리 곱해서 result라는 빈 리스트에 넣어주었다.
• 마지막으로 result 리스트에 들어간 값들의 합을 구해주었다.
• 어떻게 하면 두 배열의 누적합이 최소가 될 수 있는지만 잘 생각해내면 쉬운 문제이다.

 

<2. 다른 사람의 풀이 - (1)>

 

• 다른 사람의 풀이도 한 번 살펴보겠다.
• <방법 2>는 내가 푼 풀이와 접근 방법은 동일한데, zip 함수를 사용해서 내가 해 준 작업들을 한 줄에 끝내버렸다. (이런 스마트한 방법이 있었네..ㅎ)

 

<2. 다른 사람의 풀이 - (2)>

 

• 또 다른 사람의 풀이를 보니, map 함수와 lambda 식을 사용해서 내가 수행한 작업들을 처리해 준 것을 확인할 수 있었다. (이렇게 풀 수도 있군!)