무지의 먹방라이브 문제 바로가기
이번시간에는 먹방라이브 문제를 풀어보도록 하겠다..
비슷한 구조로 생각을 하긴 했는데, 결국 답을 보고 풀었다.
이 이야기를 하는 이유가 바로, 틀린 코드도 먼저 살펴보고 가면 좋을것 같아서이다.
자 이 문제를 딱 보자마자, 드는 생각은
K값이 2* 10^13이므로, 절대로 K값으로 for문을 돌리면 안되겠다이다.
맞는가?
처음에 생각했던것은 당연히 원형 구조의 순회이므로, queue에다가 넣고 k++시키면서 문제를 푸는것이다.
이런식으로 그럼 K번을 돌아야한다.
그렇게되면 시간복잡도가 O(K)로 거의20조번? 을 돌아야하니까 무조건 시간초과가 나오는것이다.
그래서 이 문제를 내가 접근할때 뭘하던지 절대로, K값으로 탐색을 진행하면 안되겠다라는 생각이 들었다.
그러면, 오히려 문제가 좀 쉬워지는게 남은 변수는 어차피 foods_times이므로 이 foods_times로 요리를 잘해서 해결해야겠다. 이생각 뿐이었다.
틀린문제 풀이법-효율성 1문제 통과
풀이법은 이러하다.
17초라고 치면 일단 만약 충분히 17초안에 먹을 수 없다고 가정을 하면, foods_times.size가 5라면 몫이 3 나머지가 2일것이다.
이렇게되면, 두번째 음식까지먹고, 3번째 음식이 답이 된다.
그러나 그림과 같이 x가 3개 즉 3칸을 더움직여야하니까 나머지 2+3을 해서 5칸을 움직여야한다.
그래서 몫인 3보다 큰 애들인 5,4를 -3을 빼서 queue에 2,1로 담아서 5번을 앞에서 O(k)방식이지만 k가 확 5번으로 줄어드는 방식으로 문제를 구현했다.
#include <string>
#include <vector>
#include <queue>
using namespace std;
int solution(vector<int> food_times, long long k) {
long long mod = k % food_times.size();
long long n = k / food_times.size();
long long total =0;
queue<pair<long long, long long>>q;
for(long long i=0;i<food_times.size();i++){
if(n-food_times[i]>=0){
total+=(n-food_times[i]);
}else{
q.push({-(n-food_times[i]),i+1});
}
}
total+=mod;
while(!q.empty() && total>0){
total--;
long long t1 = q.front().first;
long long t2 = q.front().second;
t1--;
q.pop();
if(t1>0){
q.push({t1,t2});
}
}
if(q.size()>0){
return q.front().second;
}else{
return -1;
}
}그런데, 이게 문제가 뭐냐면, total+=(n-food_times[i])여기에서 만약에 food_times들이 다 작다고 치면, total에다 더해지는 값이 너무 커지므로,
while문에서 toatal만큼 돌아야하는데 여기서 시간 초과가 발생하는것이다.
그래서 해결을 다르게 해야하는데,
자 height를 세로축이라고 해보자, 맨첫번쨰 음식이 있는 hegith=2 인 층을 모두 먹으려면 가로길이 foods_times.size()=5 2 10초가 필요할 것이다.
그다음 층인 3번에서 모두 먹으려면 3번 음식의 height인 4에서 방금전에 먹었던 층인 2를 빼서 4-2=2 24=8 해서 8초가 필요할 것이다.
근데 만약에 남은 k가 1이라면 어떨까?
2번의 height가 5이고 이전 hegith가 4 1*2=2인데 k가 1 이니까
k%가로 값인 k%2를 해주면 k가 1이남고 2번을 먹고 그다음인 1번이 정답이된다.
로직을 대충이렇게 잡고 코드마다 설명을 해보겠다.
vector<pair<long long,long long>> foods;
for(int i=0;i<food_times.size();i++){
foods.push_back({food_times[i],i+1});
}
sort(foods.begin(),foods.end());
int height=0;
int n = food_times.size();pair로 설정하여서 첫번째에서는 먹는데 걸리는 시간, 즉 높이를 그리고 두번째에는 몇번째가 들어가게 i+1로 하여 1번부터시작하게 하였다.
그리고 sort를 통해서 높이 순으로 오름차순해주었다.
그리고 height과 n을 설정한다.
for(int i=0;i<foods.size();i++){
long long needtime = (foods[i].first-height) * n;
if(needtime == 0){
n--;
continue;
}
if(needtime <= k){
k-=needtime;
height = foods[i].first;
}else{
k%=n;
sort(foods.begin()+i,foods.end(),comp);
return foods[i+k].second;
}
n--;
}
return -1;그다음 foods에서 순서대로 확인을 하는데
food[i].first즉 보라색 그림에서 5번에해당하는 first는 2이다.
그리고 height가 현재 0이므로 2-0은 2 고로, 5번 음식에 해당하는 모든 층을 빼기 위해서는 2*5 10초가 필요하다.
needtime==0인건 일단 넘어가고
만약에 내가 12초를 원하면 10<12이므로 k를 2로 만들고
height를 2로 설정한다.
그다음에 해당하는 3번음식에 해당하는 층을 모두빼려면 8초가 필요하다 2*4니까 근데 나는 남은 초수가 2밖에 없다. 그래서
else문으로 가서 나는 2번 음식을 먹을 기회가 있고,
sort를 내가 만든 comp를 기준으로 다시 정렬한다.
왜냐하면 이건 높이순서, 즉 음식을 먹는데 필요한 시간으로 정렬이 되어있는 상태이기 때문에
음식순서로 정렬을해야 2번 먹을 수 있다.
그래서 다시 음식순서로 정렬을 해주고, 해당하는 음식인 i에다가 2를 더하면 그다음에 먹을 음식의 차례가된다.
bool comp(pair<int,int>a,pair<int,int>b){
return a.second<b.second;
}현재 음식순서는 second에 저장이 되어있기 때문에 return a.second<로 작은게 true가 되게 설정한다.
마지막으로, ==인경우가 만약 k값이 20초라고 치자, 그러면 i가 2인 4번음식으로 온다. 근데 이미 18초를 소비하여서 4층짜리 음식을 전부 먹은 상태이므로, 18초의 상태에서는 이미 5번 3번 4번음식을 먹은 상태이다. 그래서 음식의 갯수인 n을 하나 줄여주고, 그다음에, continue로 넘어간다.
정답코드
#include <string>
#include <vector>
#include <algorithm>
#include <iostream>
using namespace std;
bool comp(pair<int,int>a,pair<int,int>b){
return a.second<b.second;
}
int solution(vector<int> food_times, long long k) {
vector<pair<long long,long long>> foods;
for(int i=0;i<food_times.size();i++){
foods.push_back({food_times[i],i+1});
}
sort(foods.begin(),foods.end());
int height=0;
int n = food_times.size();
for(int i=0;i<foods.size();i++){
long long needtime = (foods[i].first-height) * n;
if(needtime == 0){
n--;
continue;
}
if(needtime <= k){
k-=needtime;
height = foods[i].first;
}else{
k%=n;
sort(foods.begin()+i,foods.end(),comp);
return foods[i+k].second;
}
n--;
}
return -1;
}생각해보면 쉬운데, 답을 찾기 어려운 문제였다.
