c++ 26086번 어려운 스케줄링 (백준)

#include <iostream>
#include <deque>
#include <algorithm>

using namespace std;

int main(void)
{
	int n, q, k;
	scanf("%d %d %d", &n, &q, &k);
	
    //쿼리들을 저장할 배열 v[][] 왼쪽으로는 0번쿼리를 저장, 오른쪽으로는 1,2번쿼리를 저장
	int v[q][2], left = 0, right = q-1, cnt = 0;
	deque<int> deq; //나중에 사용할 덱
	
	for(int i=0; i<q; i++) { //쿼리 입력 및 저장
		int a, b;
		scanf("%d", &a);
		
		if(a==0) {
			scanf("%d", &b);
			v[left][0] = b;
			v[left++][1] = cnt++;
		}
		else {
			v[right][0] = a;
			v[right--][1] = cnt;
		}
	}

	int stop; //가장 최근에 들어온 1번 쿼리의 위치 구하기
	for(int i=right+1; i<q; i++) {
		if(v[i][0] == 1) {
			stop = i;
			break;
		}
	}
	
    //모든 쿼리들 다루기
	int j=0, out = 0; //j는 처리해야할 0번쿼리의 순서를 가리킴, out 은 처음에는 0으로 0이면 앞에서 넣고, 1이면 뒤에서 넣음
	for(int i=stop; i>right; i--) { //위에서 구했던 가장 최근의 1번쿼리가 실행 된 이후 반복문 종료
		while(v[i][1] > j) { //0번쿼리(삽입)
			if(out) deq.push_back(v[j][0]);
			else deq.push_front(v[j][0]);
			j++;
		}
		
		if(v[i][0] == 1) { //1번 쿼리
			sort(deq.begin(), deq.end()); //오름차순 정렬
			out = 0; //들어가는 방향은 앞으로 고정
		} else if(v[i][0] == 2) { //2번 쿼리
			out = (out == 0); //들어가는 방향 바꾸기 (뒤집는 것 대신)
		} 
	}
	
	for(;j<cnt; j++) { //나머지 0번쿼리들을 처리
		if(out) deq.push_back(v[j][0]);
		else deq.push_front(v[j][0]);
	}
	
	if(out) printf("%d", deq[cnt-k]); //뒤쪽 삽입인 경우
	else printf("%d", deq[k-1]); //앞쪽 삽입인 경우
}

 

풀이 : 덱, 오프라인 쿼리, 정렬

 

1. n, q, k을 입력

 

2. 이차원배열을 만든 다움 입력받은 쿼리들을 앞에서부턴 쿼리0을 뒤에서부턴 쿼리 1, 2을 저장합니다.

 

3. 쿼리 1, 2 중에서 가장 마지막에 들어온 쿼리에서부터 1번 쿼리가 나올때까지만의 쿼리만들 사용해도 됩니다 (마지막 쿼리가 1번인 경우도 있습니다) 그러므로 마지막 1,2번 쿼리로 부터 1번 쿼리가 언제 나오는지를 확인합니다.

 

이유 : 1번쿼리는 오름차순 정렬을 해버리기 때문에 이전에 시행한 1, 2번 쿼리들이 아무런 의미가 없어지게 됩니다.

 

마지막 1번 쿼리 이전의 1, 2번 쿼리들은 무시합니다.

 

4. 반복문을 이용하여 0번, 1번, 2번 쿼리들을 실행합니다.

0번인 경우 덱에 삽입합니다.

1번인 경우 오름차순 정렬 합니다.

2번인 경우 정말로 데이터 전부를 뒤집는 것이 아니라 데이터가 들어가는 입구를 바꾸어줍니다.

 

5. 만약 1, 2번 쿼리들을 해결했으나 0번쿼리가 남았다면 나머지 0번 쿼리들을 처리합니다.

 

6. 주어진 k, 그리고 현재 덱의 입구에 맞춰서 원하는 답을 출력합니다.

 

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

26086번: 어려운 스케줄링