https://school.programmers.co.kr/learn/courses/30/lessons/42587
0. Headers
#include <vector>
#include <queue>
#include <algorithm>
using namespace std;
1. 알고리즘
- 문제에서 프린터된 순서와 우선순위가 중요하므로 pair 함수를 통해 FIFO 방식인 queue 생성
- 프린터되는 순서를 담기위해 vector 생성
int solution(vector<int> priorities, int location) {
queue<pair<int, int>> q; // <순서, 우선순위>
vector<pair<int, int>> v; // 프린터
}
- <순서, 우선순위>를 담는 큐를 생성
int solution(vector<int> priorities, int location) {
int order = 0;
for (int priority : priorities)
q.push(make_pair(order++, priority));
}
- 큐가 비어있을 때 까지 수행
- 큐의 첫번 째 값
- 만약 큐에 있는 우선순위가 프린터 우선순위의 최대 값과 같으면 프린터 및 프린터 우선순위를 0으로 초기화
- 같지 않으면 FIFO방식인 맨 뒤로 집어 넣음
int solution(vector<int> priorities, int location) {
while(!q.empty())
{
auto p = q.front();
q.pop();
if(p.second == *max_element(priorities.begin(), priorities.end()))
{
v.push_back(p);
priorities[p.first] = 0;
}
else q.push(p);
}
}
- 만들어진 프린터 목록이 처음 위치해 있는 곳을 알지 못함
- 벡터를 <순서, 우선순위>로 만들었기 떄문에 처음에 위치한 순서를 알 수 있음
int solution(vector<int> priorities, int location) {
for (int i = 0; i < v.size(); i++)
if (v[i].first == location) return i + 1;
return -1;
}
2. 완성 코드
#include <vector>
#include <queue>
#include <algorithm>
using namespace std;
int solution(vector<int> priorities, int location) {
queue<pair<int, int>> q; // <순서, 우선순위>
vector<pair<int, int>> v;
int order = 0;
for (int priority : priorities)
q.push(make_pair(order++, priority));
while(!q.empty())
{
auto p = q.front();
q.pop();
if(p.second == *max_element(priorities.begin(), priorities.end()))
{
v.push_back(p);
priorities[p.first] = 0;
}
else q.push(p);
}
for (int i = 0; i < v.size(); i++)
if (v[i].first == location) return i + 1;
return -1;
}
'C++ Algorithm & Study > C++ & Algorithm Strategies' 카테고리의 다른 글
[Programmers] 삼총사 (0) | 2023.01.07 |
---|---|
[Programmers] 행렬의 덧셈 (0) | 2023.01.07 |
[Programers] 같은 숫자는 싫어 (0) | 2023.01.04 |
[Programmers] 예산 (0) | 2022.12.19 |
[Porgrammers] 영어 끝말잇기 (0) | 2022.12.17 |