[프로그래머스] 무지의 먹방 라이브 (C++)

👋 프로그래머스 <무지의 먹방 라이브> 풀이 코드 (TIL 231227)

실패 코드 (정확성 32.1)

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

using namespace std;
 
int solution(vector<int> food_times, long long k) {
    int answer = 0;
    int food_nums = food_times.size(); //음식의 개수
    vector<int> sorted_times;
    sorted_times.resize(food_nums); //food_times가 작은 순서대로 정렬된 vector
    copy(food_times.begin(), food_times.end(), sorted_times.begin());
    sort(sorted_times.begin(), sorted_times.end());
    
    int min_times_index = 0;
    int min_times = sorted_times[min_times_index];
    
    while ( k / min_times >= food_nums) {
        for (int i=0; i<food_times.size(); i++) {
            if (food_times[i] == 0) continue;
            else if (food_times[i] == min_times) {
                food_times[i] = 0;
                food_nums--;
                k -= min_times;
                min_times_index++;
            } else {
                food_times[i] -= min_times;
                k-= min_times;
            }
        }
        min_times = sorted_times[min_times_index] - sorted_times[min_times_index-1];
  
    
    int temp = 0;
    long long check = 0;
    while (k >= 0) {
        if (food_times[temp] != 0) {
            food_times[temp]--;
            k--;
            check += food_times[temp];
        }
        
        if (temp == food_times.size()-1) {
            if (check < k) {
                answer = -1;
                break;
            }
            temp = 0;
        }
        else temp++;
    }
    
    answer = temp;
    
    return answer;
}

문제점

• 처음 주어지는 food_times의 index값을 음식의 번호로 사용해야 한다는 생각에 굳이굳이... 원본 벡터는 냅두고 sorted_times라는 새로운 벡터를 생성하여 오름차순 정리를 하였다. 여기서 두 가지 벡터를 모두 다루려다 보니 오히려 헷갈리는 부분이 많았다.
• 또 이 과정에서 벡터 선언, resize, copy, sort 등 쓸데없는 시간을 많이 소요했다.
• 먹는 시간이 낮은 순으로 정렬하여 그 시간만큼 전체 vector의 원소값에서 감소시키며, 이 과정에서 다루어야 하는 food의 개수와 최소값등을 결정하는 로직 자체는 괜찮았으나, 이를 구현시키는 과정에서 부족한 점이 많았다.

💡 수정 코드

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

using namespace std;

bool cmp (pair<int, int> a, pair<int, int> b) {
    return a.second < b.second; //pair의 second를 기준으로 오름차순 
}
 
int solution(vector<int> food_times, long long k) {
    int answer = 0;
    int food_nums = food_times.size(); //음식의 개수
    int pre_min = 0; //이전단계의 min_times 값
    vector<pair<int, int>> foods;
    for (int i=0; i<food_nums; i++) {
        foods.push_back(make_pair(food_times[i],i+1)); //first: 먹는데 소요되는 시간, second: 음식의 번호
    }
    sort(foods.begin(), foods.end()); //먹는 시간을 기준으로 오름차순 정리
    
    for (vector<pair<int, int>>::iterator it=foods.begin(); it != foods.end(); ++it,--food_nums) {
        long long spend_times = (long long)(it->first - pre_min) * food_nums;
        if (spend_times == 0) continue;
        if (spend_times <= k) {
            k -= spend_times;
            pre_min = it->first;
        } else {
            k = k % food_nums;
            sort(it, foods.end(), cmp);
            return (it+k)->second;
        }
    }
    return -1;
}

수정 사항

• food_times의 각 원소값과 index값을 다루기 위해 vector<pair<int, int>> 자료형의 foods를 선언한 후 pair의 first를 먹는데 소요되는 시간, second를 음식의 번호로 저장하였다.
• iterator를 사용하여 for문을 돌면서 (해당 시간 X 음식 개수)로 k초 안에 먹을 수 있는 지를 확인한다.
  -> 여기서 생각하지 못했던 부분이 각 음식이 얼마만큼의 times이 남았는지 매번 계산해줄 필요는 없다는 것이다. 나한테 중요한 건 n번째 음식을 다 먹었는지, 아닌지이지 얼만큼 남았는지는 중요하지 않다. 또 반복자를 이용하여 반복하기 때문에 else에 도달하였을 때 it값 이전의 음식들은 다 먹은 것으로 생각할 수 있다. 그래서 sort할 때 it부터만 해주는 것!
• 위의 설명에서와 비슷하게 음식의 남은 시간을 매번 계산해주지 않기 때문에 spend_times를 구할 때 사용하는 min_times를 구할 때 it->first에서 pre_min 값을 빼주어야 한다. (이미 pre_min만큼씩 모든 원소에서 빼준 상황이기 때문)

[문제 출처] https://school.programmers.co.kr/learn/courses/30/lessons/42891
[풀이 참조] https://ansohxxn.github.io/programmers/132/