풀이
1. 인쇄 대기목록의 가장 앞에 있는 문서 J를 대기 목록에서 꺼낸다.
2. 나머지 인쇄 대기목록에서 J보다 중요도가 높은 문서가 있다면 J를 대기 목록에서 가장 마지막으로 넣는다.
3. 그렇지 않으면 J문서를 인쇄한다.앞에서 빼고, 뒤에서 다시 넣고 하는 자료구조는 Deque가 있다.
현재 가장 앞에 있는 문서의 중요도가 뒤에 있는 모든 중요도보다 높거나 같다면 그 문서를 출력하고,
아니라면 현재 가장 앞에 있는 문서를 뽑아서 뒤에 다시 넣는다.
뒤에 있는 모든 중요도 중에서 가장 높은 중요도는 어떻게 뽑을까?
간단하게 for문을 돌려 뽑을 수도 있지만 *max_element를 이용하면 쉽게 뽑아올 수 있다.
다만 시간 복잡도는 for문과 동일하지만, 간단하게 코드를 짤 수 있어서 편하고 용이하다.
#include <string>
#include <vector>
#include <deque>
#include <algorithm>
using namespace std;
int solution(vector<int> priorities, int location) {
int answer = 0;
deque<pair<int, int> > dq;
for (int i = 0; i < priorities.size(); i++) {
dq.push_back({ priorities[i], i });
}
while (!dq.empty()) {
int current_priority = dq.front().first;
int current_location = dq.front().second;
dq.pop_front();
int max_priority = (*max_element(dq.begin(), dq.end())).first;
if (current_priority >= max_priority) {
answer++;
if (current_location == location) return answer;
}
else {
dq.push_back({ current_priority, current_location });
}
}
return answer;
}'Algorithm' 카테고리의 다른 글
| [프로그래머스] [1차] 뉴스 클러스터링 (C++) (0) | 2021.05.20 |
|---|---|
| [백준 9663] N-Queen (C++) (0) | 2021.05.20 |
| [프로그래머스] 키패드 누르기 (C++) (0) | 2021.05.06 |
| [프로그래머스] 완주하지 못한 선수 (C++) (0) | 2021.04.30 |
| [프로그래머스] 크레인 인형뽑기 게임 (C++) (0) | 2021.04.30 |