[프로그래머스] 프린터 (pair, priority queue) - C++ 스택&큐

 

 

 

max_element를 이용한 풀이

max_element는 algorithm 헤더에 있는 함수다. 큐에는 사용할 수 없고, 배열에 사용할 수 있다.

형태 : *max_element(v.begin(), b.end())

int solution(vector<int> priorities, int location) {
	int answer = 0;
	queue<int> waiting;		//인덱스 큐

	for (int i = 0; i < priorities.size(); i++) {
		waiting.push(i);
	}

	int max_value = *max_element(priorities.begin(), priorities.end());
	while (!waiting.empty()) {
		int cur_index = waiting.front();
		waiting.pop();
		//맨 앞에 애 우선순위가 제일 높으면
		if (max_value == priorities[cur_index]) {
			answer++;
			priorities[cur_index] = 0;
			max_value = *max_element(priorities.begin(), priorities.end());
			if (location == cur_index) {
				return answer;
			}
		}
		else {
			waiting.push(cur_index);
		}
	}
}

 

location은 요청한 문서의 인덱스다.

우선순위를 담고 있는 벡터인 priorities의 인덱스를 담는 큐(waiting)를 만든다.

cur_index = 인덱스 큐.front() 로 인덱스를 돌린다.

max_value = *max_element(priorities.begin(), priorities.end())로 우선순위 벡터의 최대값을 담고,

max_value == priorities[cur_index] 면 프린트하므로

answer를 증가시키고, 프린트한 우선순위 벡터 값을 최소로 낮춘 후 max_value를 갱신한다.

 

우선순위 큐와 pair를 이용한 풀이

int solution(vector<int> priorities, int location) {
	int answer = 0;
	priority_queue<int> prior;
	queue<pair<int, int>> waiting;

	for (int i = 0; i < priorities.size(); i++) {
		prior.push(priorities[i]);
		waiting.push(make_pair(i, priorities[i]));
	}

	while (!waiting.empty()) {
		int index = waiting.front().first;
		int value = waiting.front().second;
		waiting.pop();

		//지금 게 우선순위가 제일 높으면
		if(prior.top() == value) {
			prior.pop();
			answer++;
                //요청한 문서와 인덱스와 같으면
			if (index == location) {
				return answer;
			}
		}
                //아니면 뒤로 돌려보내기
		else {
			waiting.push(make_pair(index, value));
		}
	}
}

 

우선순위의 최대값을 스택처럼 top()으로 뽑을 수 있는 우선순위 큐 prior를 만든다.

인덱스와 우선순위 값을 페어로 가지는 큐 waiting을 만든다.

최대값을 prior.top()으로 뽑아서 waiting 큐 맨앞의 우선순위값과 비교한다.

최대면 answer++를 하고 최대값 큐를 pop 해서 최대값을 갱신한다.

이 때 프린트한게 요청한 문서의 인덱스면 리턴한다.