[프로그래머스/Day 13] 과일 장수 - O(N log N)이 통과되는 이유와 O(N) 풀이법

오늘은 프로그래머스 '과일 장수' 문제를 풀면서 겪었던 고민과 해결 과정을 공유하려고 합니다.

특히, "이중 for문을 썼는데 왜 시간 복잡도가 O(N²)이 아닐까?" 라는 의문과 index 및 계수 정렬을 통한 효율적인 접근 방식에 대해 정리해 보았습니다.

1. 문제 개요

이 문제는 사과의 점수가 담긴 배열 score, 한 상자에 담을 사과 개수 m, 사과의 최대 점수 k가 주어졌을 때, 얻을 수 있는 최대 이익을 계산하는 문제입니다.

• 사과들을 점수에 따라 잘 조합해 상자(m개)를 만들어야 합니다.
• 상자의 가격은 (상자에 담긴 최저 사과 점수) x m 입니다.
• 제한 사항: score의 길이는 최대 100만입니다.

---

2. 첫 번째 접근: sort + pop_back 활용

입력값이 100만 개라 효율성이 중요했습니다.

일단 가장 이익을 많이 내려면 점수가 높은 사과끼리 묶어야 하므로 정렬을 해야겠다고 판단했습니다.

그 후, 뒤에서부터 m개씩 꺼내(pop) 상자를 만드는 시뮬레이션 코드를 작성했습니다.

// k = 사과 하나의 최대 점수
// m = 한 상자에 담는 사과의 개수
// 과일 장수가 판매할 수 있는 상자 개수 = 사과의 전체 개수 / 한 상자에 담는 사과의 개수

// 1. 과일 장수가 판매할 수 있는 상자 개수 boxCount를 구한다.
// 2. 사과들의 점수인 score를 오름차순 정렬한다.
// 3. boxCount만큼 다음 과정을 반복한다.
// 4. m개만큼 score에서 내보낸다.
//    - 마지막으로 내보낸 값을 최저 사과 점수로 한다.
// 5. 최저 사과 점수 * m을 결과에 더한다.

#include <algorithm>
#include <string>
#include <vector>

using namespace std;

int solution(int k, int m, vector<int> score) {
    int answer = 0;

    // 1. 과일 장수가 판매할 수 있는 상자 개수 boxCount를 구한다.
    int boxCount = score.size() / m;

    // 2. 사과들의 점수인 score를 오름차순 정렬한다.
    sort(score.begin(), score.end());

    // 3. boxCount만큼 다음 과정을 반복한다.
    for(int i = 0; i < boxCount; ++i)
    {
        // 4. m개만큼 score에서 내보낸다.
        for(int j = 0; j < m; ++j)
        {
            // - 마지막으로 내보낸 값을 최저 사과 점수로 한다.
            if(j == m - 1)
            {
                int minAppleScore = score.back();

                // 5. 최저 사과 점수 * m을 결과에 더한다.
                answer += minAppleScore * m; 
            }

            score.pop_back();
        }
    }

    return answer;
}

의문점: 이중 for문인데 왜 시간 초과가 안 날까?

보통 이중 for문은 O(N²)의 시간 복잡도를 가진다고 생각하기 쉽습니다.

N=1,000,000일 때 N²이면 시간 초과가 나야 정상인데, 이 코드는 통과합니다.

이유는 반복 횟수의 총합을 계산해보면 알 수 있습니다.

• 바깥쪽 루프: 상자 개수만큼 반복 → (N / m)번
• 안쪽 루프: 한 상자에 담는 개수만큼 반복 → m번

두 반복 횟수를 곱하면 전체 연산 횟수가 나옵니다.

즉, pop_back()은 정확히 전체 사과 개수(N)만큼만 수행됩니다.

따라서 이 부분의 시간 복잡도는 O(N)이며, 정렬 시간인 O(N log N)이 총 시간 복잡도가 되어 통과할 수 있었던 것입니다.

---

3. 두 번째 접근: sort + Index 활용

첫 번째 방식도 통과하지만, 굳이 벡터의 원소를 삭제(pop_back)하며 메모리를 건드릴 필요는 없습니다.

내림차순 정렬 후 인덱스만 계산하면 훨씬 깔끔합니다.

// 1. 점수를 내림차순 정렬한다.
// 2. m개씩 건너뛰며 해당 위치의 점수를 확인한다.
//    - 내림차순이므로 (i + m - 1)번째 인덱스가 그 상자의 최저 점수가 된다.

#include <algorithm>
#include <vector>

using namespace std;

int solution(int k, int m, vector<int> score) {
    int answer = 0;

    // 1. 점수를 내림차순 정렬한다.
    sort(score.begin(), score.end(), greater<int>());

    // 2. m개씩 건너뛰며 해당 위치의 점수를 확인한다.
    for (int i = 0; i + m <= score.size(); i += m) {

        // - 내림차순이므로 (i + m - 1)번째 인덱스가 그 상자의 최저 점수가 된다.
        answer += score[i + m - 1] * m;
    }

    return answer;
}

---

4. 세 번째 접근: 문제의 특성을 이용한 O(N) 풀이

만약 N이 1억 개라면 O(N log N)도 부담될 수 있습니다.

이때는 "사과 점수 k는 3 이상 9 이하"라는 제한 사항에 주목해야 합니다.

점수 범위가 매우 작으므로, 계수 정렬(Counting Sort) 아이디어를 쓰면 정렬 없이 풀 수 있습니다.

계수 정렬(Counting Sort)이란?

일반적인 정렬(퀵 정렬, 병합 정렬 등)은 두 값을 '비교'해서 자리를 바꿉니다.

하지만 계수 정렬은 비교하지 않습니다. 대신 각 숫자가 몇 번 등장했는지 개수를 셉니다.

• 원리: 점수(값)를 배열의 인덱스로 보고, 해당 인덱스의 카운트를 1씩 증가시킵니다.
• 예시: [1, 3, 3, 2]가 입력이라면,
  • 1번 인덱스: 1개
  • 2번 인덱스: 1개
  • 3번 인덱스: 2개
• 장점: 값의 범위가 작을 때, O(N)이라는 압도적인 속도를 자랑합니다.

문제에 적용하기

우리는 사과를 줄 세울 필요 없이, "3점짜리 몇 개, 4점짜리 몇 개..." 인지만 알면 됩니다.

또한, 이 방식은 원본 배열을 정렬(수정)하지 않고 읽기만 하면 되므로, 참조(const &)를 사용하여 메모리 복사 비용까지 아낄 수 있습니다.

단, 이 문제에서 매개변수의 수정은 허용되지 않으므로 그대로 작성했습니다.

1. 카운팅: counts 배열을 만들어 각 점수별 사과 개수를 저장합니다.
2. 역순 탐색: 가장 높은 점수(k)부터 내려오며 상자를 만듭니다.
3. 이월(Leftover): 상자를 만들고 남은 사과는 버리는 게 아니라, 다음(더 낮은) 점수의 사과들과 합쳐서 상자를 구성합니다.

#include <vector>
using namespace std;

int solution(int k, int m, vector<int> score) {
    int answer = 0;

    // 각 점수(1~k)별 사과 개수를 센다. (O(N))
    vector<int> counts(k + 1, 0);
    for(int s : score) {
        counts[s]++;
    }

    // 높은 점수부터 상자를 채운다. (O(k))
    int leftover = 0;
    for(int i = k; i >= 1; --i) {
        // 현재 점수 i의 사과 개수 + 이전 점수에서 남아서 내려온 사과
        int currentCount = counts[i] + leftover;

        // 만들 수 있는 상자 수
        int boxNum = currentCount / m;

        // 이익 계산 (현재 점수 i가 이 상자들의 최저 점수가 됨)
        answer += boxNum * m * i;

        // 상자에 담지 못하고 남은 사과는 다음(더 낮은) 점수 처리에 합류
        leftover = currentCount % m;
    }

    return answer;
}

성능 분석

• 시간 복잡도: 사과 전체 순회 O(N) + 점수 범위 순회 O(k). 최종적으로 O(N)입니다.
  N이 커질수록 O(N log N) 방식과 성능 차이가 벌어집니다.
• 공간 복잡도: 점수 범위만큼의 배열만 필요하므로 O(k)입니다.
  (위 코드에서는 참조를 사용하지 못하므로 O(N))

결국 "값의 범위가 작다"는 특성을 파악하면, 정렬 없이도 더 빠르고 효율적인 풀이가 가능합니다.

---

5. 정리

1. 이중 Loop의 함정: "이중 for문 = O(N²)"이라는 공식에 갇히지 말아야 합니다. 전체 수행 횟수가 N에 비례한다면 O(N)입니다.
2. 데이터 수정 최소화: vector의 구조를 변경(pop, erase)하는 것보다, 가능하다면 인덱스(Index)로 접근하는 것이 더 깔끔하고 빠릅니다.
3. 복잡도 판단: N=100만일 때, O(N log N)은 충분히 안전한 복잡도입니다.