카카오2019 - 무지의 먹방라이브

phoenixKim·2021년 7월 25일

알고리즘 카카오코테

카카오 기출문제

목록 보기

1/24

몇번 풀어봄?

21년 10월 05일 화요일

풀이 전략

문제를 읽어보고 순차적으로 하려고 했으나, 생각해보니 k값이 long long이므로 다름 방법을 생각해야 했다.
추가적으로 food_times의 원소는 10억개이므로 logN으로 나타낼수 있는 stl을 사용해야 한다.
걸리는 시간이 작은 번호를 먼저 제외해 나간후, 남아 있는 번호들 간의 순서를 파악하는 방식으로 할 수 있다.
-> 왜냐하면 큼지막하게 뺌으로써 문제에 접근하기가 쉬워진다.

그렇다고 해서 시간 큰 놈을 먼저 빼면 k의 조건처리에 걸리고, 큰놈 * size만큼 빼야 하는데,
작은 친구의 빈공간은 어떻게 처리할지에 대해 생각을 하면 작은 친구 부터 빼야 한다는 것을 생각해낼 수 있다.
=> 결론 : 우선순위큐 - 내림차순으로 해놓고, top부분부터 지워나가자.

정말 중요한점.

전체 소요시간을 측정하는 변수가 있어야 한다.
우선순위 큐는 모든 컨테이너에 참조할 수 없으므로, 몇번 순회를 했는지를
측정하는 변수가 있어야 한다. 이변수를 통해 추후의 값 비교가 가능하다.

끄적 끄적

참고 안하고 푼 코드

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

struct compare
{
    public : 
    
    bool operator()(pair<int,int>a, pair<int,int>b)
    {
        return a.second > b.second;
    }
};

bool compare2(pair<int,int>a, pair<int,int>b)
{
    return a.first < b.first;
}

int solution(vector<int> food_times, long long k) {
    int answer = 0;
    
    long long sum = 0;
    for(const auto i : food_times)
        sum += i;
    
    if(sum <= k)
        return -1;
    
    //인덱스 번호 - 소요 시간
    priority_queue<pair<int,int>,vector<pair<int,int>>, compare>pq;
    
    for(int i = 0; i < food_times.size(); i++)
    {
        pq.push({i + 1, food_times[i]});
    }
    
    long long totalTime = 0;
    long long totalCnt = 0;
         
    while( (k - totalTime ) >= pq.size() * ( pq.top().second - totalCnt )  ) 
    {
        int cnt = pq.top().second - totalCnt;
        //이후의 남겨진 pq의 소요시간을 줄이기 위한 변수...
        totalCnt += cnt;         
        //제거 될때마다 cnt값은 달라진다. 
        totalTime += pq.size() * cnt;      
        pq.pop();        
    }
   
    //나열시키자.
    vector<pair<int,int>>v;
    
    while(!pq.empty())
    {
        v.push_back({pq.top().first, pq.top().second});       
        pq.pop();
    }
    
    //일단 오름차순으로 정렬하자.
    sort(v.begin(), v.end(), compare2);
    
    long long spareTime = k - totalTime;
    long long index = (spareTime) % v.size();
    answer = v[index].first;
    
    return answer;
}