탐욕법. [1026]

[1. 문제 설명]

[2. 풀이 접근]

완전 탐색 시 시간복잡도는 N!

=> 현실적인 시간내에서 해결이 불가능함.

두 수의 곱들의 합을 최소로 만들기 위한 방법을 생각해보면

문제 조건 상 두 수의 곱이 음수가 될 수 없다.

즉, 모든 두 수의 곱이 최소가 되도록 하면 된다.

수열 B 의 순서는 재배열하지 않는다고 적혀있지만, 정렬해도 된다.

(단, 수열 A 를 출력하라고 한다면, 원래 위치를 따로 저장 할 필요가 있다.)

정렬 후 수열 B 의 앞쪽에 오는 숫자는 가장 작은 값 이다.

여기에 수열 A 에서 가장 큰 값을 곱하도록 한다.

가장 작은 값을 곱하면, 수열 B의 가장 큰 값에 수열 A 에서 가장 큰 값이 곱해 질 수 있다.

=> 큰 값 끼리의 곱이 영향이 전체 합에서 가장 큰 부분을 차지 하게 된다.

즉, 수열 B 를 오름차순으로 정렬하고,

수열 A 를 내림차순으로 정렬한 순서이고,

이 상태에서 각 index 에 해당하는 원소 간 곱들의 합이 원하는 답을 구하게 해준다.

정렬하는 시간이 전체 시간복잡도가 된다.

O(nlogn)

[3. 코드]

test_kernelv2