프로그래머스. 최솟값 만들기

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

코딩테스트 연습 - 최솟값 만들기

 

n이 1000까지여서 처음에 그냥 브루트포스로 풀었다

next_permutation 함수를 중첩된 형태로 풀었는데 next_permutation 함수가 O(n)이므로 될줄알았다.

그런데 생각해보니 각 수들을 곱하는 과정에서 또 n의 반복문이 필요하므로 O(n^3)이 되버려서 실패.

 

그냥 얌전히 그리디로 풀기로 했다.

큰 숫자가 작은 숫자와 곱해져야 작은 수가 나올것이므로 두 개의 벡터를 각각 오름차순, 내림차순 정렬 후 곱한다.