[백준/C++] 1966번 프린터큐
2021. 1. 29. 15:49ㆍ알고리즘/구현
728x90
반응형
문제: www.acmicpc.net/problem/1966
1966번: 프린터 큐
여러분도 알다시피 여러분의 프린터 기기는 여러분이 인쇄하고자 하는 문서를 인쇄 명령을 받은 ‘순서대로’, 즉 먼저 요청된 것을 먼저 인쇄한다. 여러 개의 문서가 쌓인다면 Queue 자료구조에
www.acmicpc.net
문제풀이
첫 번째로 문제에 접근한 방식은 큐와 배열을 선언하여 큐에는 pair로 문서의 인덱스, 중요도를 쌍으로 저장하고
배열에는 중요도를 저장 후 내림차순 정렬(sort 함수)하여 배열과 큐의 중요도를 비교했다.
- 중요도가 같을 때
1. 목표 문서라면(인덱스가 같다면) 현재 출력 순서 출력 후 루프 종료
2. 현재 가장 높은 중요도를 가진 문서이므로 pop() 후 출력 순서 증가, 배열 인덱스 증가
- 중요도가 다를 때
현재 큐의 front()에 있는 문서보다 높은 중요도를 가진 문서가 큐 안에 있으므로 현재 문서를 큐의 맨 뒤로 보냄
코드
#include <iostream>
#include <queue>
#include <algorithm>
using namespace std;
bool compare(int num1, int num2){ //내림차순
return num1>num2;
}
int main(){
ios::sync_with_stdio(false); cin.tie(NULL);
int T;
cin>>T;
int N, M;
queue<pair<int,int>> q;
for(int i=0; i<T; i++){
cin>>N>>M;
int impo[N];
for(int j=0; j<N; j++){
cin>>impo[j];
q.push({j, impo[j]});
}
sort(impo, impo+N, compare); //내림차순 정렬
int result=1;
int index=0;
while(!q.empty()){
if(impo[index]==q.front().second){ //중요도 검사
if(q.front().first==M){ //인덱스까지 같으면 결과 출력 후 루프 종료
cout<<result<<"\n";
q = queue<pair<int,int>>(); //큐 초기화...
break;
}
q.pop();
index++;
result++;
}
else{
q.push(q.front()); //중요도가 더 높은 문서가 있으므로 맨뒤로
q.pop();
}
}
}
return 0;
}
결과
오답이 많은데 중간에 큐를 초기화를 안 해줘서 헤맸었습니다.
728x90
반응형
'알고리즘 > 구현' 카테고리의 다른 글
[백준/C++] 2108번 통계학 (0) | 2021.02.04 |
---|---|
[백준/C++] 2164번 카드2 (0) | 2021.02.03 |
[백준/C++] 10989번 수 정렬하기 3 (0) | 2021.02.03 |
[백준/C++] 1929번 소수 구하기 (0) | 2021.02.03 |
[백준/C++] 15829번 Hashing (0) | 2021.02.02 |