programmers 무지의 먹방 라이브

programmers 무지의 먹방 라이브 : programmers.co.kr/learn/courses/30/lessons/42891#qna

코딩테스트 연습 - 무지의 먹방 라이브

level3에 해당하는 문제였지만 저는 푸는데 되게 오래 걸린 문제입니다..

풀고나니 어렵지 않은 문제같은 느낌이 ㅠㅠ;

 

저는 정렬을 이용해서 문제를 해결했습니다.

새로운 벡터에 <음식의 양, 인덱스> 로 초기화하고

음식의 양을 기준으로 정렬을 합니다.

예시를 들어 설명하겠습니다.

[8,4,6], 15 일때

정렬을 하면 [4,6,8]가 됩니다.

가장 작은 값인 4라는 음식을 통해서 아래와 같은 값을 구할 수 있습니다.

(먹을 수 있는 음식의 갯수)*(현재 음식의 양 - 마지막으로 먹은 음식의 양)

이를 canK 라고 할 때, canK는 결국 순회가능한 횟수를 말합니다. 

처음에 4를 통해 canK는 3*(4-0) = 12라는 값을 얻을 수 있고, 

주어진 k는 15이기 때문에 순회가 가능하게 됩니다.

그 다음 작은 값 6에서 canK는 2*(6-4) = 4가 됩니다.

원래 k=16에서 정상적으로 다 먹어지는 음식인 6은 현재 k가 15이기 때문에 다 먹지 못하게 됩니다.

여기서 답을 구하기 위한 계산에 들어갑니다.

 

현재 먹을 수 있는 음식은 2개[8,6]

현재까지 순회한 횟수 cntk = 12

2개의 음식을 (15-12)=3번 먹는다 => 3%2 = 1

즉 1번째 음식까지는 먹을 수 있고 그 다음 음식이 무엇인지만 알면 됩니다.

 

주석을 통해 나머지 설명을 하겠습니다.

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

int solution(vector<int> food_times, long long k) {
    int answer = -1;
    
    // 정렬과 인덱스 값을 알기 위해 새로운 벡터를 만듬
    vector<pair<int, int> > food;
    for (int i = 0; i < food_times.size(); i++) {
        food.push_back({ food_times[i], i });
    }

    // 정렬해줌
    sort(food.begin(), food.end());

    // 순회한 횟수 cntK
    long long cntk = 0;
    // 마지막으로 먹은 음식인 lastFood
    int lastFood = 0;
    for (int f = 0; f < food.size(); f++) {
        // 당장 먹어야하는 음식의 양 => 음식의 양 - 마지막으로 먹은 음식의 양
        int eatFood = food[f].first - lastFood;
        // food의 인덱스
        int food_idx = food[f].second;
        
        // 순회할 수 있는 횟수 canK는
        // 현재 음식의 양에 남은 음식의 size를 곱한 것!
        long long cank = (food.size()-f) * eatFood;
        
        // k초 안으로 순회가 가능하다면
        if(cntk + cank <= k){
            cntk += cank;
            lastFood = food[f].first;
            food[f].first = 0;
            food_times[food_idx] = 0;
        }
        // 순회가 불가능하다면
        else{
            // temp는 최종적으로 순회할 음식에 대한 나머지 값
            int temp = (k - cntk) % (food.size() - f);
            // 나머지 값에 대한 카운트 변수 check
            int check = 0;
            for(int i = 0; i<food_times.size(); i++){
                // 없는 음식은 먹지 않아도 된다
                if(food_times[i] == 0) continue;
                // 나머지 값과 같다면 이 음식이 현재 먹어야하는 음식!
                if(check == temp){
                    answer = i;
                    return answer+1;
                }
                check++;
            }
        }
    }

    return answer;
}