백준 - 26086 어려운 스케줄링

문제

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

26086번: 어려운 스케줄링

stack 구조의 스케쥴러를 이용해 명령을 수행하고 k번째로 처리할 업무를 찾는 문제였다.

 

명령은 다음과 같다.

0 p : 스케줄러의 맨 앞에 번호 p인 업무를 추가한다.
1 : 스케줄러의 업무를 p 기준으로 오름차순 정렬한다.
2 : 스케줄러의 업무 처리 순서를 뒤집는다.

명령 횟수는 100000, 시간 제한은 1초였다.

 

문제 풀이

명령 횟수가 100000이기 때문에 정렬이 나올 때마다 수행하게 된다면 무조건 시간 초과가 날 것 같았다.

 

스케줄러에 입력만 된다는 것에 집중했다. 입력만 들어오기 때문에 정렬은 마지막 한 번만 실행하면 된다. 따라서 전체 정렬 중 한 번만 수행해도 같은 결과가 나온다. 또, 뒤집는 것은 deque를 이용했다.

 

먼저 정렬 명령어의 맨 마지막 순서를 저장하고, 그 전까지는 0번 명령만 수행하며 무조건 벡터 뒤에 추가했다. 마지막 정렬 순서가 되면 정렬한 후에 deque에 넣었다. 정렬 이후부터는 순서 뒤집기가 나오면 isFront를 바꿔주고 추가할 때는 isFront에 맞게 앞/뒤에 추가했다.

 

이때, 정렬이 한 번도 나오지 않았다면 처음부터 deque에 넣으면서 정렬 이후 과정대로 진행했다.

 

정답은 isFront에 맞게 해당 위치를 k-1번 pop 해주고, 마지막 k번째의 맨 앞, 혹은 맨 뒤가 된다.

 

int N, Q, k;
vector<int> arr; //정렬 전 저장
deque<int> d; 
vector<pair<int, int>> oper; //연산자 저장
int lastSortIndex; //마지막 정렬 위치
bool isFront; //true -> 포인터가 앞, fasle -> 포인터가 뒤

int main() {

	scanf("%d %d %d", &N, &Q, &k);

	oper = vector<pair<int, int>>(Q);

	lastSortIndex = Q + 1;
	for (int i = 0; i < Q; i++) {
		int type, num;
		num = -1;
		scanf("%d", &type);
		if (type == 0) {
			scanf("%d", &num);
		}
		oper[i] = { type, num };
		if (type == 1) {
			lastSortIndex = i;
		}
	}

	isFront = true;

	//lastSortIndex 전까지는 arr에 저장, 이후에는 deque에 저장
	if (lastSortIndex == Q + 1) { //정렬이 한 번도 나오지 않을 경우
		for (int i = 0; i < Q; i++) {
			if (oper[i].first == 0) {
				if (isFront) d.push_front(oper[i].second);
				else d.push_back(oper[i].second);
			}
			else {
				if (isFront) isFront = false;
				else isFront = true;
			}
		}
	}
	else {
		for (int i = 0; i < Q; i++) {
			if (i < lastSortIndex) { //arr에 넣기
				if (oper[i].first == 0) {
					arr.push_back(oper[i].second);
				}
				else if (oper[i].first == 2) {
					if (isFront) isFront = false;
					else isFront = true;
				}
			}
			else if (i == lastSortIndex) { // 1번 정렬 후 deque에 넣기
				sort(arr.begin(), arr.end());
				for (int i = 0; i < arr.size(); i++) {
					d.push_back(arr[i]);
					isFront = true;
				}
			}
			else { //deque에 저장			
				if (oper[i].first == 0) {
					if (isFront) d.push_front(oper[i].second);
					else d.push_back(oper[i].second);
				}
				else {
					if (isFront) isFront = false;
					else isFront = true;
				}
			}
		}
	}

	/*
	printf("\n---------------------\n");
	for (int i = 0; i < N; i++) {
		printf("%d ", d.back());
		d.pop_back();
	}
	*/
	


	for (int i = 0; i < k-1; i++) {
		if (isFront) {
			d.pop_front();
		}
		else {
			d.pop_back();
		}
	}

	int answer;

	if (isFront) answer = d.front();
	else answer = d.back();

	printf("%d", answer);
	
	return 0;
}

/*
*/