[프로그래머스] 카카오 무지의 먹방 라이브 c++

programmers.co.kr/learn/courses/30/lessons/42891

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

 

기본적인 아이디어.

 

1. 시간(k초)안에 회전판에 남아있는 음식(n개) 중 가장 적은 양의 음식(mfood)을 공략한다.

2. 가장 적은 양의 음식이 사라지고 다시 회전판은 처음으로 돌아온다.

3. 그때 남은 시간은 k= k-(mfood*n);

4. 1번을 k-(mfood*n)>=0 될 때 까지 반복한 후 5번.

5. 남은 k초 동안의 인덱스를 구한다. 

 

세부적인 아이디어.

 

가장 적은 양의 음식을 공략해야 하므로 별도로 food_times를 오름차순으로 정렬한다(인덱스도 함께 기억).

인덱스 계산할 시 % 연산으로 실행시간을 줄인다.

 

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

bool cmp(vector <int> a, vector <int> b)
{
    return a[1]<b[1];
}

https://programmers.co.kr/learn/courses/30/lessons/42891
int solution(vector<int> food_times, long long k) {
    int answer = 0;
    int n = food_times.size();
    vector<vector <int>> food;
    
    
    for(int i=0; i<food_times.size(); i++)
    {
        vector <int> temp;
        temp.push_back(food_times[i]);
        temp.push_back(i);
        food.push_back(temp);
    }
    
    sort(food.begin(),food.end());

    
    for(int i=food.size()-1; i>0; i--)
    {
        food[i][0]-=food[i-1][0];
    }
    
    
    int sw=0;
    for(int i=0; i<food.size(); i++)
    {
        
        if(food[i][0]*n<=k)
        {
            k-=(long)food[i][0]*n; 
            n--;
        }
        else
        {
            sort(food.begin()+i,food.end(),cmp);
            answer=food[i+k%n][1]+1;
            sw=1;
            
            break;
        }
        
    }
    
    if(sw==0) answer=-1;
    
    
    return answer;
}

무지의 먹방 실행시간