[G3] 백준 26086번 어려운 스케줄링 C++ 오프라인 쿼리, 덱, 정렬

리뷰

 

https://www.acmicpc.net/problem/26086

쿼리가 들어왔을 때 마다 처리해 주는건 당연히 시간이 터질 것 같았지만 한번 내봤다.

 

 

전역 변수

• n : 작업 고유번호의 제한값을 저장할 변수
• q : 쿼리의 개수를 저장할 변수
• k : 최종 출력할 작업의 인덱스를 저장할 변수
• deq : 작업 순서를 저장할 덱
• OP : 작업 종류 op, op가 0일 경우 작업 번호 val을 정의할 구조체
• ops : 작업 정보를 저장할 OP타입 배열
• last1 : 마지막 정렬 작업의 인덱스를 저장할 변수

 

함수

없음

 

 

문제풀이

1. n, q, k값을 입력 받고, q번의 for문을 개행해 q개의 쿼리를 입력 받아준다.
2. 변수 op에 작업의 종류를 입력 받아준다.
3. op가 0일 경우 변수 num에 작업의 고유 번호를 추가로 입력 받은 후 ops[i]에 op, num을 저장해  준다.
4. op가 1일 경우 ops[i]에 op를 저장해 주고, 변수 last1에 i값을 저장해 준다.
5. op가 2일 경우 ops[i]에 op를 저장해 준다.
6. 쿼리를 모두 입력 받은 후에는 다시 q번의 for문을 개행해 쿼리를 순회해 준다.
7. 현재 처리해야할 op가 0이라면 deq의 앞쪽에 val을 push해준다.
8. op가 1이면서 last1과 i가 같다면, deq을 오름차순으로 정렬해 준다.
9. op가 2이면서 last1보다 크다면 deq을 reverse처리해 준다.
10. 모든 작업을 마친 후 deq의 k - 1번째 값을 출력해 준다.

 

트러블 슈팅

1. 쿼리가 들어올 때 마다 sort, reverse처리를 해주면 시간이 터진다, 골드 문제면 이를 원하진 않았을 것이다.
2. 오프라인 쿼리를 통해 필요할 때만 sort, reverse처리를 해주니 간단하게 AC를 받았다.

 

참고 사항

• 마지막 정렬 작업 전까진 정렬이나 reverse작업을 수행해 줄 필요가 없다.
• 마지막 정렬 작업 이후의 reverse도 cnt를 세어 짝수번까지의 reverse작업은 해줄 필요가 없어 보인다. 이를 적용하면 시간 복잡도를 더욱 줄일 수 있을 것 같다.

 

정답 코드

#include<iostream>
#include<algorithm>
#include<deque>
using namespace std;

int n, q, k;
deque<int> deq;
struct OP {
	int op, val;
};
OP ops[100000];
int last1;

int main() {
	ios::sync_with_stdio(0);
	cin.tie(0);

	cin >> n >> q >> k;
	for (int i = 0; i < q; ++i) {
		int op; cin >> op;
		if (op == 0) {
			int num; cin >> num;
			ops[i] = { op, num };
		}
		else if (op == 1) {
			ops[i] = { op };
			last1 = i;
		}
		else if (op == 2) {
			ops[i] = { op };
		}
	}

	for (int i = 0; i < q; ++i) {
		const OP& op = ops[i];
		if (op.op == 0) deq.push_front(op.val);
		else if (op.op == 1 && i == last1) sort(deq.begin(), deq.end());
		else if (op.op == 2 && i > last1) reverse(deq.begin(), deq.end());
	}
	cout << deq[k - 1];
}