문제 URL : https://programmers.co.kr/learn/courses/30/lessons/42891
코딩테스트 연습 - 무지의 먹방 라이브
programmers.co.kr
문제 접근법 :
k번째에 누가 먹어야하는지 묻는 문제입니다.
그냥 조건대로하다간 시간초과가 발생할테니 가장빠른 방법을 선택해야합니다.
음식을 먹는시간과 인덱스를 가지고 pair를 통해서 정렬한후
food_time와 남아있는 사이즈를 곱하여 k와의 차이를구하여 k가 더 작을때까지
한다음 다시 인덱스로 정렬하여
남아있는 k가 몇번째 주기동안 왔다갔다 할수있는 지묻는문제입니다.
소스코드 :
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
|
#include <bits/stdc++.h>
using namespace std;
#define ll long long
bool cmp(pair<ll, int> a, pair<ll, int> b) {
return a.second < b.second;
}
int solution(vector<int> food_times, long long k) {
ll sum = 0;
deque<pair<ll, int>> dq;
for (int i = 0; i < food_times.size(); i++) {
dq.push_back({ food_times[i],i });
sum += (ll)food_times[i];
}
if (sum <= k) return -1;
sort(dq.begin(), dq.end());
ll before = 0;
while (!dq.empty()) {
ll val = dq.size() * (dq.front().first - before);
if (val > k)
break;
k -= val;
before = dq.front().first;
dq.pop_front();
}
sort(dq.begin(), dq.end(), cmp);
int ans = dq[k % dq.size()].second;
return ans+1;
}
|
cs |
궁금한점 혹은 모르는점 논리적인 오류등 어떤질문이든 댓글은 언제나 환영입니다.
공감 눌러주실꺼죠?
'프로그래머스' 카테고리의 다른 글
| 프로그래머스 [1차]프렌즈4블록(2018 KAKAO BLIND RECRUITMENT) (0) | 2021.09.08 |
|---|---|
| 프로그래머스 올바른 괄호의 갯수 (0) | 2021.09.07 |
| 프로그래머스 [1차] 셔틀버스(2018 KAKAO BLIND RECRUITMENT) (0) | 2021.09.05 |
| 프로그래머스 블록 게임(2019 KAKAO BLIND RECRUITMENT) (0) | 2021.09.04 |
| 프로그래머스 매칭 점수(2019 KAKAO BLIND RECRUITMENT) (0) | 2021.09.01 |
