무지의 먹방 라이브 (C++, 2019 카카오 블라인드 채용)[프로그래머스]

안녕하세요 멍청한 토끼입니다.

이번 문제는 2019 카카오 블라인드 채용 문제에 있는

Lv4 무지의 먹방 라이브 문제 입니다.

 

※ 저의 풀이가 무조건적인 정답은 아닙니다.

다른 코드가 좀더 효율적이고 좋을 수 있습니다.

다른사람들의 풀이는 언제나 참고만 하시기 바랍니다.

문제 주소입니다.

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

코딩테스트 연습 - 무지의 먹방 라이브 | 프로그래머스

 

---

목차

1. 문제 설명

2. 문제 해석

3. 소스 코드

3.1 주석 없는 코드

3.2 주석 있는 코드

3.3 테스트 코드

4. 결과

 

---

1. 문제 설명

평소 식욕이 왕성한 무지는 자신의 재능을 뽐내고 싶어 졌고 고민 끝에 카카오 TV 라이브로 방송을 하기로 마음먹었다. 그냥 먹방을 하면 다른 방송과 차별성이 없기 때문에 무지는 아래와 같이 독특한 방식을 생각해냈다. 회전판에 먹어야 할 N 개의 음식이 있다. 각 음식에는 1부터 N 까지 번호가 붙어있으며, 각 음식을 섭취하는데 일정 시간이 소요된다. 무지는 다음과 같은 방법으로 음식을 섭취한다. 무지는 1번 음식부터 먹기 시작하며, 회전판은 번호가 증가하는 순서대로 음식을 무지 앞으로 가져다 놓는다. 마지막 번호의 음식을 섭취한 후에는 회전판에 의해 다시 1번 음식이 무지 앞으로 온다. 무지는 음식 하나를 1초 동안 섭취한 후 남은 음식은 그대로 두고, 다음 음식을 섭취한다. 다음 음식이란, 아직 남은 음식 중 다음으로 섭취해야 할 가장 가까운 번호의 음식을 말한다. 회전판이 다음 음식을 무지 앞으로 가져오는데 걸리는 시간은 없다고 가정한다.

 

문제!!

무지가 먹방을 시작한 지 K 초 후에 네트워크 장애로 인해 방송이 잠시 중단되었다. 무지는 네트워크 정상화 후 다시 방송을 이어갈 때, 몇 번 음식부터 섭취해야 하는지를 알고자 한다. 각 음식을 모두 먹는데 필요한 시간이 담겨있는 배열 food_times, 네트워크 장애가 발생한 시간 K 초가 매개변수로 주어질 때 몇 번 음식부터 다시 섭취하면 되는지 return 하도록 solution 함수를 완성하라.

 

제한사항

food_times 는 각 음식을 모두 먹는데 필요한 시간이 음식의 번호 순서대로 들어있는 배열이다. k 는 방송이 중단된 시간을 나타낸다. 만약 더 섭취해야 할 음식이 없다면 -1을 반환하면 된다. 정확성 테스트 제한 사항 food_times 의 길이는 1 이상 2,000 이하이다. food_times 의 원소는 1 이상 1,000 이하의 자연수이다. k는 1 이상 2,000,000 이하의 자연수이다. 효율성 테스트 제한 사항 food_times 의 길이는 1 이상 200,000 이하이다. food_times 의 원소는 1 이상 100,000,000 이하의 자연수이다. k는 1 이상 2 x 10^13 이하의 자연수이다.

 

예시

food_times	K	return
[3, 1, 2]	5	1
[8, 6, 4]	15	2
[946, 314, 757, 322, 559, 647, 983, 482, 145]	1833	1

 

입출력 예 #1 0~1초 동안에 1번 음식을 섭취한다. 남은 시간은 [2,1,2] 이다. 1~2초 동안 2번 음식을 섭취한다. 남은 시간은 [2,0,2] 이다. 2~3초 동안 3번 음식을 섭취한다. 남은 시간은 [2,0,1] 이다. 3~4초 동안 1번 음식을 섭취한다. 남은 시간은 [1,0,1] 이다. 4~5초 동안 (2번 음식은 다 먹었으므로) 3번 음식을 섭취한다. 남은 시간은 [1,0,0] 이다. 5초에서 네트워크 장애가 발생했다. 1번 음식을 섭취해야 할 때 중단되었으므로, 장애 복구 후에 1번 음식부터 다시 먹기 시작하면 된다.

 

---

2. 문제풀이

# 삽질 이야기

1. 처음에는 단순하게 새로운 벡터를 생성하고 pair를 이용하여 음식의 번호와 시간을 넣고 반복문을 이용하여 k가 0이 될때까지 음식의 시간을 감소시키고, 음식시간이 0이 되면 벡터에서 제거하는 형식으로 진행했습니다. 정확성 테스트는 통과했으나 효율성 테스트에서 떨어졌습니다.   2. 두번째는 우선순위 큐를 이용하여 제일 적은시간이 들어있는 음식의 시간만큼 모든 음식에서 시간을 뺏습니다. 제일적은 시간을 가진음식이 5초라면 모든음식에서 5초를 제외하는 방식이었습니다. k가 줄어드는 숫자는 제일작게 남은음식 * 음식의 숫자로 위에보다는 빠른연산이 가능했지만 효율성 테스트에서 떨어졌습니다.   3.  K의 숫자를 빠르게 떨어트리는것에 중점을 두고 생각을 했습니다.  두번째 풀이를 약간 변형하여 풀었더니 효율성 테스트를 통과했습니다. 풀이는 아래와 같습니다.

최종 문제풀이

#벡터 혹은 우선순위큐를 이용해서 푸시면 됩니다. 어떤것을 이용해도 상관없습니다. 저는 우선순위 큐를 이용하여 풀었습니다. 처음에는 방송이 중단된 후 먹을 음식이 있는지 없는지를 판단하기 위해 들어온 food_times를 우선순위큐<음식시간, 음식번호>>로 옮기는 과정에서 sum에 더해줍니다. 이때 우선순위 큐는 min heap 으로 만들어줍니다. (처음에 기본 min heap줄알고 만들었다가 max 힙이 기본이여서 시간을 날렸습니다.) (구현이 귀찮다면 -를 이용하여 뒤집으시면 됩니다.) 만약 sum이 k보다 적거나 같다면 sum<=k -1을 리턴합니다. ------------------------------------------------------------------------------------------------------------- 이제 여기부터가 중요합니다. times = [8, 6, 4], k =15,answer = 2 를 가지고 예를 들어보겠습니다. 제일 작은 음식은 4초입니다. 3번째 음식이 사라지는 시간은 [4(제일적은 음식시간) * 3(총 음식 갯수)] 입니다. 즉 12초가 지나야 3번째 음식이 사라집니다. k에서 12초를 제외합니다. 그러면 times 는 [8,6] k = 3이 남습니다. 그다음 작은 음식은 6인데 전음식을 없애기위해 4바퀴를 돌았으므로 [{ 6 (제일적은 음식시간) - 4 (이전에 돌았던 음식시간) ) } * 2 (총 음식 개수) 를 k에서 빼줍니다. 원래라면 16초에서 2번째 음식을 다먹는 시간이지만 k가 0보다 작거나 같아진다면 음식을 뺄수없는 상황입니다. 그렇다면 남은 음식에 k를 총 음식개수로 나머지 연산해서 인덱스 번호를 반환하면 끝이납니다. k가 3이 남았으므로 2로 나머지 연산을 하면 1이나오고 인덱스 1번은 2번 음식입니다. 15초동안 음식테이블을 돌면서 검증을 해보도록 하겠습니다. ------------------------------------------------------------------------------------------------------------- 1초 [7, 6, 4] - 2초 [7, 5, 4] - 3초 [7, 5, 3] - 4초 [6, 5, 3] -5초 [6, 4, 3] - 6초 [6, 4, 2] - 7초 [5, 4, 2] - 8초 [5, 3, 2] - 9초 [5, 3, 1] - 10초 [4, 3, 1] - 11초 [4, 2, 1] - 12초 [4, 3, 0](3번째 음식 사라짐) - 13초 [3, 2, 0] - 14초 [3, 1, 0], - 15초 [2, 1, 0](방송중단, 마지막은 1번음식을 먹었으므로 다음은 2번음식) 16초 [2, 0, 0] (2번음식 다먹음) 위에서 계산한 방법과 같습니다.(참고는 나동빈(동빈 나)님의 유튜브를 참고했습니다.) 링크 : https://youtu.be/Rgw0fo6isUM?t=1036

---

3. 소스코드

3.1 주석없는 코드

#include <string>
#include <vector>
#include <algorithm>
#include <queue>
 
using namespace std;
 
int solution(vector<int> food_times, long long k) {
    long long sum = 0, before = 0;
    priority_queue<pair<int, int>> pfood_times;
    for (int i = 0; i < food_times.size(); i++) {
        sum += food_times[i];
        pfood_times.push(make_pair(-food_times[i], (i + 1)));
    }
    if (sum <= k)    return -1;
    while ((-pfood_times.top().first - before) * pfood_times.size() <= k) {
        k -= (-pfood_times.top().first - before) * pfood_times.size();
        before = -pfood_times.top().first;
        pfood_times.pop();
    }
    vector<pair<int, int>> ftimes;
    while (!pfood_times.empty()) {
        ftimes.push_back(make_pair(pfood_times.top().second, -pfood_times.top().first));
        pfood_times.pop();
    }
    sort(ftimes.begin(), ftimes.end());
    return ftimes[k % ftimes.size()].first;
}

3.2 주석있는 코드

#include <string>
#include <vector>
#include <algorithm>
#include <queue>
 
using namespace std;
 
int solution(vector<int> food_times, long long k) {
    long long sum = 0, before = 0;  //합과 이전값 저장용
    priority_queue<pair<int, int>> pfood_times; //우선순위 큐
    //우선순위 큐로 옮기면서 합확인(min heap을 위해 -로 반전)
    for (int i = 0; i < food_times.size(); i++) {
        sum += food_times[i];
        pfood_times.push(make_pair(-food_times[i], (i + 1)));
    }//총시간이 K보다 적거나 같다면 -1을 리턴
    if (sum <= k)    return -1;
    //작은 음식만큼 시간을 소요하는데 걸리는 시간은 (현재 제일작은 음식 - 이전음식값 * 총 음식개수) 이다.
    //이 시간만큼 K를빼주고 음식도 뺀다.(계산할때 -넣었어서 뒤집는다)
    while ((-pfood_times.top().first - before) * pfood_times.size() <= k) {
        k -= (-pfood_times.top().first - before) * pfood_times.size();
        before = -pfood_times.top().first;
        pfood_times.pop();
    }//반복문이 끝났다면 순서대로 파악한다.
    vector<pair<int, int>> ftimes;
    //편한 파악을 위해 vector로 옮긴다.
    while (!pfood_times.empty()) {
        //정렬 비교함수를 만들기 귀찮으니까 pair를 뒤집어준다.
        ftimes.push_back(make_pair(pfood_times.top().second, -pfood_times.top().first));
        pfood_times.pop();
    }
    //원래 순서대로 정렬한다.
    sort(ftimes.begin(), ftimes.end());
    //나머지 연산으로 위치찾고 반환
    return ftimes[k % ftimes.size()].first;
}

3.3 테스트 코드 추가

#include <string>
#include <vector>
#include <algorithm>
#include <iostream>
#include <queue>
 
using namespace std;
 
int solution(vector<int> food_times, long long k) {
    long long sum = 0, before = 0;  //합과 이전값 저장용
    priority_queue<pair<int, int>> pfood_times; //우선순위 큐
    //우선순위 큐로 옮기면서 합확인(min heap을 위해 -로 반전)
    for (int i = 0; i < food_times.size(); i++) {
        sum += food_times[i];
        pfood_times.push(make_pair(-food_times[i], (i + 1)));
    }//총시간이 K보다 적거나 같다면 -1을 리턴
    if (sum <= k)    return -1;
    //작은 음식만큼 시간을 소요하는데 걸리는 시간은 (현재 제일작은 음식 - 이전음식값 * 총 음식개수) 이다.
    //이 시간만큼 K를빼주고 음식도 뺀다.(계산할때 -넣었어서 뒤집는다)
    while ((-pfood_times.top().first - before) * pfood_times.size() <= k) {
        k -= (-pfood_times.top().first - before) * pfood_times.size();
        before = -pfood_times.top().first;
        pfood_times.pop();
    }//반복문이 끝났다면 순서대로 파악한다.
    vector<pair<int, int>> ftimes;
    //편한 파악을 위해 vector로 옮긴다.
    while (!pfood_times.empty()) {
        //정렬 비교함수를 만들기 귀찮으니까 pair를 뒤집어준다.
        ftimes.push_back(make_pair(pfood_times.top().second, -pfood_times.top().first));
        pfood_times.pop();
    }
    //원래 순서대로 정렬한다.
    sort(ftimes.begin(), ftimes.end());
    //나머지 연산으로 위치찾고 반환
    return ftimes[k % ftimes.size()].first;
}
 
 
void print(vector<int> food_times, long long k, int answer) {
    int t = solution(food_times, k);
    if (answer == t)
        cout << "정답" << endl;
    else
        cout << "틀림" << endl;
}
 
int main() {
    print({ 3,1,2 }, 5, 1);
    print({ 8,6,4 }, 15, 2);
    print({ 946, 314, 757, 322, 559, 647, 983, 482, 145 }, 1833, 1);
 
    return 0;
}

4. 결과