해당 문제는 특정 금액이 존재할 때, 해당 금액에 딱 맞추어 물품을 최대한 많이 구매해줘야 하는 문제이다.
여기서 중요한 쟁점은 크게 두 가지라고 볼 수 있다.
: 최대한 많은 물품을 구매하는 방법을 확인하는 것은 매우 간단하다.
가장 작은 인덱스 값부터 차례대로 확인하는 방법이다.
가장 작은 인덱스 값부터 차례대로 확인하기 위해서는 정렬을 해야 한다.
| 정렬 방식 | 시간 복잡도 | |
|---|---|---|
| Arrays.sort() | DualPivotQuicksort | 평균 : O(nlog(n)) / 최악 : O(n^2) |
| Collections.sort() | TimeSort (삽입정렬과 합병정렬을 결합한 정렬) | 평균, 최악 : O(nlog(n)) |
알아보니, 정렬 방식에는 두 가지가 존재한다. 기본적으로 우리가 가진 데이터는 Array이기 때문에, 최악의 경우 O(n^2)의 시간 복잡도를 가지게 된다.
이를 줄이기 위해서는 정렬에서 최소한의 시간복잡도를 갖는 Collections.sort() 를 활용해야 한다.
확인해보니, Collections는 객체만을 받아서 사용할 수 있다고 한다.
이를 위해 우리는 Array와 ArrayList의 차이를 이해해야 한다.