[프로그래머스/알고리즘] 무지의 먹방 라이브

무지의 먹방 라이브

저는 왜 이런게 어려울까요.

입출력 예

food_times : [3,1,2]

k : 5

result : 1

해결방법

보면 문제가 굉장히 쉬울 줄 알았습니다만 큐에다가 원하는걸 food_times 인덱스들을 담고 k를 1개씩 검사하는 알고리즘으로 채점을 하면 시간초과로 틀려버렸습니다, 이리저리 해매다가 코드가 복잡해버려졌네요.

제가 생각하는 방법은 k를 한바퀴씩 가야되겠다고 생각했습니다.

예제를 보면 1번 음식이 3번이기 때문에 1번음식을 기준으로 한바퀴씩 돌려야 한다고 생각했습니다.

가장 큰 인덱스를 구하는 max_index를 구했습니다.

여기서 인덱스가 중간에 있으면 0번부터 max_index까지 1번씩은 섭취했기 때문에 food_times를 1개씩 빼야 했습니다.

그리고 한바뀌 돌때마다 더이상 섭취할 수 없는 음식이 생깁니다. 이것들을 확인하기 위해서 우선순위큐에 담았고 

남은 음식 수(우선순위 큐에 남은것)들은 remain변수에 저장했습니다.

한바퀴 돌때 더하는 값은 remain을 이용해서 current(제가 찾고자 하는 값)을 증가시키는데 current가 k보다 커지면 height바퀴에 남아있는 음식아니면 height-1바퀴에 남아있는 음식 중에 있다고 생각했습니다. 이 2라인을 이전 current값을 이용해서 정답을 구했습니다.

소스코드

#include <string>
#include <vector>
#include <queue>
using namespace std;
int solution(vector<int> food_times, long long k) {
    long long answer = 0;
		
    priority_queue<int, deque<int>, greater<int>> data;			//처음 갯수 확인
	int max_index = 0;
	long long current = 0;
	long long previous;
	int remain = food_times.size();
	int height = 1;

	for (int j = 0; j < food_times.size(); j++) { // 가장 큰 인덱스 찾기
		if (food_times[j] > food_times[max_index]) {
			max_index = j;
		}							
	}
		
	for (int i = 0; i < max_index; i++) { // 1번음식부터 인덱스까지 1번 먹고 큐에 담음

		if (food_times[i] - 1 == 0)
			remain--;
		else {
			data.push(food_times[i] - 1);
		}
	}
		
	for (int i = max_index + 1; i < food_times.size(); i++) {  //인덱스 그다음부터 큐에 담음

		data.push(food_times[i]);
	}
			
	current = max_index;
	previous = 0;
		
	for (long long i = food_times[max_index]; (k-1)/food_times.size() >= 0&&k>=current; i--) {
		previous = current;
		current += remain; //한바퀴 돌때마다 remain값을 도해줌

		while (!data.empty()&&height == data.top()) {   //height바퀴 : 먹은 횟수, 우선순위 큐에 다 먹으면 버려야함
			remain--;
			data.pop();
		}
		height++;
			
	}

	for (int i = max_index; i < food_times.size()&&height-1>0; i++) { // height-1 라인에 있는 k값 조사
		if (food_times[i] >= height - 1) {
			if (previous == k)
				return i + 1;

		previous++;
	    }
    }


	for (int i = 0; i <= max_index; i++) {     // height 라인에 있는 k값 조사
		if (food_times[i] >= height) {
			if (previous == k)
				return i + 1;
			previous++;
		}
	}
	return -1;
}