X - [ 그리디 ] 무지의 먹방 라이브 - R

난이도 : 하  풀이시간 : 30/155ㅅㅂ  시간제한 : 1초  기출 : 2019 카카오 신입 공채

문제 링크

 

 

::  코딩테스트 연습 - 무지의 먹방 라이브 | 프로그래머스 (programmers.co.kr)

 

---

  아이디어  

못풀어서 클론코딩 함 다음 기회에 ~

 

  내   코드  

  내   코드  

 

 

  정답  코드  

#include <iostream>
#include <vector>
#include <algorithm>
#include <queue>
#include <string>

using namespace std;


int solution(vector<int> food_times, long long k) {

    vector<int> v;
    for (int i = 0; i < food_times.size(); i++) {
        v.push_back(food_times[i]);
    }

    sort(v.begin(), v.end());
    int foodLeft = food_times.size(); // 남은 음식 수
    int cnt_min = 0; // 최소시간을 가지는 음식의 종류
    int min = v[0]; // 최소값
    int pr_min = 0; // 이전 최소값
    int it = 0; // 벡터를 순회할 인덱스

    while (1) {
        if (foodLeft <= 0) {
            return -1;
        }
        if (it < v.size() && v[it] == min) { // 최소값을 가지는 음식갯수 세기
            it++;
            cnt_min++;
            continue;
        }
        if (k - 1ll * foodLeft * (min - pr_min) >= 0) {
            k -= 1ll * foodLeft * (min - pr_min);
            foodLeft -= cnt_min;
        }
        else {
            // min 보다 큰 k번째 원소 찾기
            k %= foodLeft;
            int i;
            for (i = 0; k >= 0; i = (i + 1) % food_times.size()) {
                if (food_times[i] <= pr_min) continue;
                k--;
            }
            i = i == 0 ? food_times.size() : i;
            return i;
        }
        cnt_min = 0;
        pr_min = min;
        min = v[it];
    }
    return -1;
}


int main() {

    vector<int> v1 = { 3, 1, 2 }; long long k1 = 5; // 1
    vector<int> v2 = { 3, 0, 0 }; long long k2 = 5; // -1
    vector<int> v3 = { 3, 2, 5 }; long long k3 = 5; // 3
    vector<int> v4 = { 1, 0, 1 }; long long k4 = 5; // -1
    vector<int> v5 = { 3, 4, 5 }; long long k5 = 11; // 3

    //printf("result : %d\n", solution(v1, k1));
    printf("%d %d %d %d %d \n", solution(v1, k1), solution(v2, k2), solution(v3, k3), solution(v4, k4), solution(v5, k5));
}

 

#include <bits/stdc++.h>

using namespace std;

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

int solution(vector<int> food_times, long long k) {
    // 전체 음식을 먹는 시간보다 k가 크거나 같다면 -1
    long long summary = 0;
    for (int i = 0; i < food_times.size(); i++) {
        summary += food_times[i];
    }
    if (summary <= k) return -1;
    
    // 시간이 작은 음식부터 빼야 하므로 우선순위 큐를 이용
    priority_queue<pair<int, int> > pq;
    for (int i = 0; i < food_times.size(); i++) {
        // (음식 시간, 음식 번호) 형태로 우선순위 큐에 삽입
        pq.push({-food_times[i], i + 1});
    }
    
    summary = 0; // 먹기 위해 사용한 시간
    long long previous = 0; // 직전에 다 먹은 음식 시간
    long long length = food_times.size(); // 남은 음식의 개수

    // summary + (현재의 음식 시간 - 이전 음식 시간) * 현재 음식 개수와 k 비교
    while (summary + ((-pq.top().first - previous) * length) <= k) {
        int now = -pq.top().first;
        pq.pop();
        summary += (now - previous) * length;
        length -= 1; // 다 먹은 음식 제외
        previous = now; // 이전 음식 시간 재설정
    }

    // 남은 음식 중에서 몇 번째 음식인지 확인하여 출력
    vector<pair<int, int> > result;
    while (!pq.empty()) {
        int food_time = -pq.top().first;
        int num = pq.top().second;
        pq.pop();
        result.push_back({food_time, num});
    }
    sort(result.begin(), result.end(), compare); // 음식의 번호 기준으로 정렬
    return result[(k - summary) % length].second;
}

  리뷰