연습문제 > 과일 장수

문제 위치 : https://school.programmers.co.kr/learn/courses/30/lessons/135808

프로그래머스

처음 보면서 다음과 같은 풀이법이 떠올랐다.

 

가장 먼저 정렬을 한다.

이후 정렬된 점수들을 작은 배열로 묶어가면 최솟값을 찾는다.

모든 사과를 포장할 때까지 배열을 묶음을 만든다.

 

라는 방식으로 풀 계획이었다. 거기에 더해 algorithm 함수가 주어지지 않은 만큼 이를 사용하지 않기 위해 quick_sort 함수를 직접 구현하여 풀기로 하였다. 

#include <string>
#include <vector>

using namespace std;

// Partition 함수 (중간값 피벗 선택)
int partition(vector<int>& arr, int low, int high) {
    int mid = low + (high - low) / 2; // 중간값 피벗
    swap(arr[mid], arr[high]); // 피벗을 마지막으로 이동

    int pivot = arr[high];
    int i = low - 1;

    for (int j = low; j < high; ++j) {
        if (arr[j] > pivot) { // 내림차순 정렬
            ++i;
            swap(arr[i], arr[j]);
        }
    }
    swap(arr[i + 1], arr[high]);
    return i + 1;
}

// QuickSort 구현
void quickSort(vector<int>& arr, int low, int high) {
    if (low < high) {
        if (high - low < 10) { 
            // 삽입 정렬로 작은 배열 처리
            for (int i = low + 1; i <= high; ++i) {
                int key = arr[i];
                int j = i - 1;
                while (j >= low && arr[j] < key) { // 내림차순 삽입 정렬
                    arr[j + 1] = arr[j];
                    --j;
                }
                arr[j + 1] = key;
            }
        } else {
            int pivotIndex = partition(arr, low, high);
            quickSort(arr, low, pivotIndex - 1);
            quickSort(arr, pivotIndex + 1, high);
        }
    }
}

// Solution 함수
int solution(int k, int m, vector<int> score) {
    int answer = 0;
    int s_len = score.size();
    if (s_len < m) return 0;

    quickSort(score, 0, s_len - 1); // 내림차순 정렬
    
    for (int i = 0; i < s_len / m; ++i) {
        int minScore = score[(i + 1) * m - 1]; // 묶음의 최소값
        answer += minScore * m;
    }

    return answer;
}

 

하지만 위 풀이의 경우 실제 동작에서 문제가 생겼다.

정렬하는데 너무나 많은 시간이 걸려 시간 초과가 발생하는 것이었다.

 

이를 위해 고민하다가 score의 갯수를 전부 사과의 갯수초 치환하면 된다는 사실이 떠올랐다.

 

이 때 k의 범위가 0~9이므로 10의 배열을 불러 이를 score에서 각 점수의 사과를 모두 세주었다.

그런 다음 가장 높은 점수의 사과부터 순회를 시작한다.

 

그런 다음 각 점수에서 (점수별 가능한 묶음 갯수) * (한 묶음의 갯수) * (현재 묶음의 점수)를 정답에 더해주었다.

이후 남은 사과들은 무조건 이보다 이하의 사과로 취급되므로 한 단계 낮은 사과에 그 수만큼 더해주었다.

 

아래는 이를 구현한 코드이다.

#include <string>
#include <vector>

using namespace std;

int solution(int k, int m, vector<int> score) {
    int answer = 0;
    int quality[10] = {0};
    for(int s : score){
        quality[s]+=1;
    }
    for(int i = k; i >= 1; i--){
        answer+= (quality[i]/m) * m * i;
        quality[i-1]+= quality[i]%m;
    }
    
    return answer;
}

 

수정하기 이전보다 훨씬 간결해졌고 깔끔해졌다.

 

다른 사람의 풀이를 보니 <algorithm> 라이브러리를 사용한 경우가 많이 보였다.

그런 사람들도 처음의 나와 비슷한 풀이를 사용하였지만 라이브러리를 사용하여 성공한 것으로 보였다.

 

하지만 정렬 알고리즘의 보편적인 시간 복잡도는 항상 O(nlogn)이다.

그런데 내가 짠 방식대로 하면 시간 복잡도는 O(n)에 불과하다.

 

앞으로도 문제를 풀이하는데 있어 주어진 라이브러리만을 최대한 활용하는 습관을 들여야겠다.