I. 과일장수 문제
https://school.programmers.co.kr/learn/courses/30/lessons/135808#
1. 문제 설명
과일 장수가 사과 상자를 포장하고 있습니다. 사과는 상태에 따라 1점부터 k점까지의 점수로 분류하며, k점이 최상품의 사과이고 1점이 최하품의 사과입니다. 사과 한 상자의 가격은 다음과 같이 결정됩니다.
- 한 상자에 사과를 m개씩 담아 포장합니다.
- 상자에 담긴 사과 중 가장 낮은 점수가 p (1 ≤ p ≤ k)점인 경우, 사과 한 상자의 가격은 p * m 입니다.
과일 장수가 가능한 많은 사과를 팔았을 때, 얻을 수 있는 최대 이익을 계산하고자 합니다.(사과는 상자 단위로만 판매하며, 남는 사과는 버립니다)
- (최저 사과 점수) x (한 상자에 담긴 사과 개수) x (상자의 개수) = 2 x 4 x 1 = 8
사과의 최대 점수 k, 한 상자에 들어가는 사과의 수 m, 사과들의 점수 score가 주어졌을 때, 과일 장수가 얻을 수 있는 최대 이익을 return하는 solution 함수를 완성해주세요.
2. 제한 사항
- 3 ≤ k ≤ 9
- 3 ≤ m ≤ 10
- 7 ≤ score의 길이 ≤ 1,000,000
- 1 ≤ score[i] ≤ k
3. 풀이
과일 장수가 최대로 이익을 얻기 위해선 상대적으로 높은 가치를 지닌 사과들을 같은 박스에 담고, 상대적으로 낮은 가치를 지닌 사과들을 같은 박스에 담아야한다. 왜냐하면 낮은 가치를 지닌 사과들과 높은 가치를 지닌 사과들이 섞일 경우, 높은 가치를 지닌 사과의 가격은 낮은 가치를 지닌 사과와 동일하게 취급되기 때문이다.
결론적으로, 다음과 같이 진행했다.
1. 사과의 score를 입력받는다.
2. score[]를 내림차순으로 정렬한다.
3. m(한 상자에 들어가는 사과의 수)에 따라 score[]를 나눈다.
4. 나눠진 사과들 중 가장 낮은 점수에 m을 곱하고, 그 총합을 리턴한다.
4. 소스 코드
4-1) FruitVendor.java
public class FruitVender {
public static void main(String[] args) {
int result = 0;
Scanner scanner = new Scanner(System.in);
int m = 0; // 한 상자에 들어갈 사과의 갯수
int amount = 0; // 포장할 사과의 갯수
int k = 0; // 사과 점수의 최댓값
int[] scores = null; // 사과 점수 array
// User Input
while( m < 3 || m > 10){
System.out.print("한 상자에 들어갈 사과의 수를 입력하시오.(3~10) > ");
m = scanner.nextInt();
scanner.nextLine(); // scanner buffer 초기화
}
while (amount < 7 || amount > 1000000){
System.out.print("포장할 사과의 갯수를 입력하시오.(7~1000000) > ");
amount = scanner.nextInt();
scanner.nextLine(); // scanner buffer 초기화
scores = new int[amount];
}
while (k<1 || k>9){
System.out.print("사과 점수의 최댓값을 입력하시오(3~9). > ");
k = scanner.nextInt();
scanner.nextLine(); // scanner buffer 초기화
}
for (int i = 0; i < amount; i++){
int score = 0;
while (score <= 0 || score > k){
System.out.printf("%d번째 사과의 점수를 입력하시오.(1~%d) > ", i+1, k);
score = scanner.nextInt();
scanner.nextLine(); // scanner buffer 초기화
scores[i] = score;
}
}
// 정렬을 위해 Class SortedArray 생성
SortedArray sortedScores = new SortedArray(scores, amount);
// score[i]를 삽입 정렬(내림차순)
sortedScores.InsertionSortD();
for (int i = 0; i < amount/m; i++){
int worstApple = 10; // 사과의 최고 점수는 7이므로, 10으로 초기화
// 사과 박스 가격 선정(worstApple * m)
for (int j = 0; j < m; j++){
if (worstApple > sortedScores.array[m*i+j]){
// 상자에 담긴 사과 수 * 담긴 사과 중 최저 점수
worstApple = sortedScores.array[m*i+j];
}
}
result = result + worstApple * m;
}
System.out.printf("Result: %d\n", result);
}4-2) SortedArray.java
package programmers.fruit_vender;
public class SortedArray {
// field
int[] array = null;
int size;
String type = null;
// constructor
public SortedArray(int[] passedArray, int passedSize){
array = passedArray;
size = passedSize;
}
// tools
void Swap(int tmp1, int tmp2){
int tmp = array[tmp1];
array[tmp1] = array[tmp2];
array[tmp2] = tmp;
}
// Algorithms
public void SelectionSortA(){
for (int i = 0; i<size ; i++){
int min = i;
// 현재 자리부터 가장 작은 숫자 찾음
for (int j = i+1; j<size; j++){
if(array[min] >= array[j]){
min = j;
}
}
// 가장 작은 숫자와 현재 자리 바꿈
if (i != min){
Swap(i, min);
}
}
type = "SelectionSorted_Ascending";
}
public void SelectionSortD(){
long start = System.currentTimeMillis();
for (int i = 0; i<size ; i++){
int max = i;
for (int j = i+1; j<size; j++){
if(array[max] <= array[j]){
max = j;
}
}
if (i != max){
Swap(i, max);
}
}
type = "SelectionSorted_Descending";
long end = System.currentTimeMillis();
System.out.println(type + " 실행 시간 : " + (end-start));
}
}II. Selection Sort
1. 개념
1) 제자리 정렬(in-place sorting) 알고리즘
해당되는 배열 외에 다른 추가적인 메모리를 요구하지 않는 정렬 방법.
2) 과정
- 주어진 배열 중 최솟값을 찾는다.
- 최솟값을 첫 번째 위치한 값과 교체한다.
- 첫 번째 값을 제외한 나머지 배열 중 최솟값을 찾는다.
- 나머지 배열 중 최솟값을 찾는다.
- 나머지 배열의 첫 번째 값에 최솟값을 넣는다.
3) Selection Sort(선택 정렬)의 시간복잡도
정렬해야 하는 원소가 n개라고 가정했을 때,
- 첫번째 사이클 : 1 ~ n-1 번째 원소와 비교 => n-1번 비교
- 두번째 사이클 : 2 ~ n-1 번째 원소와 비교 => n-2번 비교
- 세번째 사이클 : 3 ~ n-1 번째 원소와 비교 => n-3번 비교
(...중략...) - n-1 번째 사이클 : n번째 원소와 비교 => 1번 비교
총 비교 횟수는,
(n-1) + (n-2) + (...중략...) + 2 + 1 = n(n-1)/2번.
결론적으로 시간복잡도는 O(n^2)이다.
4) 구현
public void SelectionSortA(int[] array, int size){
for (int i = 0; i<size ; i++){
int min = i;
for (int j = i+1; j<size; j++){
if(array[min] >= array[j]){
min = j;
}
}
if (i != min){
Swap(i, min);
}
}
type = "SelectionSorted_Ascending";
}III. Insertion Sort
1. 개념
배열의 모든 요소를 앞에서부터 차례로 이미 정렬된 부분과 비교하여 삽입하는 알고리즘.
1) 과정
- 주어진 배열 중 두 번째에 위치한 값을 확인하고 Key 값으로 설정한다.
2-1. 첫 번째 배열과 Key 값을 비교하여, Key 값이 크다면 해당 자리를 유지한다.
2-2. 첫 번째 배열과 Key 값을 비교하여, Key 값이 작다면 첫 번째 저장된 배열을 한 칸 오른쪽 배열에 저장한다.
2-3. Key 값을 첫 번째 배열에 저장한다. - 주어진 배열 중 세 번째에 위치한 값을 확인하고 Key 값으로 설정한다.
4-1. 두 번째 배열과 Key 값을 비교하여, Key 값이 크다면 해당 자리를 유지한다.
4-2. 두 번째 배열과 Key 값을 비교하여, Key 값이 작다면 두 번째 저장된 배열을 한 칸 오른쪽 배열에 저장한다.
4-2-1. 첫 번째 배열과 Key 값을 비교하여, Key 값이 크다면 두 번째 배열에 저장한다.
4-2-2. 첫 번째 배열과 Key 값을 비교하여, Key 값이 작다면 첫 번째 저장된 배열을 한 칸 오른쪽 배열에 저장한다.
4-2-2-1. 첫 번째 배열에 Key 값을 저장한다.
(이후 n번째 배열까지 동일 논리로 실행한다.)
2) Insertion Sort(선택 정렬)의 시간복잡도
2-1) 최선의 경우(이미 정렬이 완료된 경우)
- 비교는 각 배열의 원소마다 한 번씩 이루어진다.
정렬해야 하는 원소가 n개라고 가정했을 때, 시간복잡도는 O(n)이다.
2-2) 최악의 경우(역순으로 정렬된 경우)
각 배열의 모든 원소는, 본인보다 앞에 위치한 모든 원소와 비교를 시행한다.
정렬해야 하는 원소가 n개라고 가정했을 때,
- 첫번째 사이클 : 1 ~ n-1 번째 원소와 비교 => n-1번 비교
- 두번째 사이클 : 2 ~ n-1 번째 원소와 비교 => n-2번 비교
- 세번째 사이클 : 3 ~ n-1 번째 원소와 비교 => n-3번 비교
(...중략...) - n-1 번째 사이클 : n번째 원소와 비교 => 1번 비교
총 비교 횟수는,
(n-1) + (n-2) + (...중략...) + 2 + 1 = n(n-1)/2번.
결론적으로 시간복잡도는 O(n^2)이다.
IV. System.currentTimeMillis()
호출된 시간을 long 형태로 나타내는 메소드. 코드의 실행에 사용되는 시간을 확인하는 데 응용할 수 있다.
long start = System.currentTimeMillis();
(실행 시간을 확인하고자 하는 Code)
long end = System.currentTimeMillis();
System.out.println(type + " 실행 시간 : " + (end-start));V. Selection Sort VS Insertion Sort
오늘 풀었던 알고리즘 예제를 사용해 Selection Sort와 Insertion Sort의 차이를 비교해보았다.
1. 조건
총 10만개의 난수를 사용했으며, 난수의 범위는 예제의 조건에 맞추어 1~7로 제한했다.
2. 결과
SelectionSorted_Descending 실행 시간 : 9542
InsertionSorted_Ascending 실행 시간 : 7133. 분석
난수가 1~7까지로, 비교의 대상이 되는 숫자가 적어 Insertion Sort가 압도적으로 빨랐다. Selection Sort의 경우, 크기가 동일한 원소 역시도 위치를 Swap하는 특징이 있는데 이 때문에 대비가 뚜렷했던 것으로 보인다.
