[내배캠 TIL 260316] C++ 과일 장수 문제

1. 처음 작성한 코드

#include <string>
#include <vector>
#include <algorithm>
using namespace std;

int solution(int k, int m, vector<int> score) {
    int answer = 0;
    
    sort(score.begin(), score.end());
    
    while(score.size() >= m)
    {
        int minScore = k;
        for(int i = 0 ; i < m ; ++i)
        {
            if(score[score.size() - 1] < k) 
            {
                minScore = score[score.size() - 1];
            }
            score.pop_back();
        }
        answer += minScore*m;
    }
    
    return answer;
}

---

 

2. 문제점

    1. 불필요한 반복 구조

while(score.size() >= m)
{
    for(int i = 0 ; i < m ; ++i)

• while 안에서 다시 for문을 돌기 때문에 구조적으로 2중 반복이 된다.
• 실제로는 묶음의 최소값만 알면 되는데 m번 반복하며 pop을 수행하고 있다.

---

    2. vector를 계속 수정하는 구조

score.pop_back();

• 상자를 만들 때마다 vector에서 요소를 제거하고 있다.
• 코딩 테스트에서는 보통 자료구조를 변경하기보다 인덱스를 활용하는 방식이 더 단순하고 안전하다.

---

    3. 최소값 계산 방식이 부정확

if(score[score.size() - 1] < k)
{
    minScore = score[score.size() - 1];
}

• minScore를 k로 시작해서 비교하는 방식은 논리적으로 맞지 않다.
• 실제로 필요한 값은 묶음 안에서의 최소 점수이다.

---

 

3. 개선 아이디어

점수를 내림차순 정렬하면
각 상자에서 마지막 원소가 최소값이 된다.

예시

score = [1,2,3,4,5,6,7]
m = 3

 

-- 내림차순 정렬
[7,6,5,4,3,2,1]

 

 -- m개씩 묶음
[7,6,5] -> 최소 5
[4,3,2] -> 최소 2

즉 m번째 위치의 값이 항상 최소값이 된다.

---

 

4. 개선된 코드

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

using namespace std;

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

    sort(score.begin(), score.end(), greater<int>());

    for(int i = m - 1; i < score.size(); i += m)
    {
        answer += score[i] * m;
    }

    return answer;
}

---

 

5. 개선 결과

항목기존 코드개선 코드

반복 구조	while + for	for 하나
vector 수정	pop_back 사용	인덱스 접근
최소값 계산	조건 비교	정렬 후 위치로 결정
가독성	복잡	단순

---

 

6. 배운 점

• 문제에서 묶음의 규칙이 있다면 인덱스 패턴을 먼저 찾는 것이 중요하다.
• vector를 계속 수정하기보다 정렬 후 인덱스 접근 방식이 더 효율적이다.
• 코딩 테스트에서는 로직을 단순하게 만드는 것이 가장 큰 최적화다.