CAT6

문제: https://www.acmicpc.net/problem/7662

처음에는 두개의 우선순위 큐를 사용하면 되지 않을까 했지만, 반례가 발생해서 안됐다.

그 다음 deque을 사용해야하나 했지만 우선 순위가 적용되지 않아 안됐고, 이후 map을 생각하게 됐다.

STL의 map은 이진 탐색 트리로 구현이 되어있으면서, begin과 end로 최댓값, 최솟값을 가져올 수 있기 때문에 적절하다고 판단했다. key가 insert되는 실제 값이고 value는 해당 값의 count다.

#include <iostream>
#include <algorithm>
#include <map>

using namespace std;

int main() {
	int t; cin >> t;

	while (t-- > 0) {
		int k; cin >> k;

		map<int, int, greater<int>> que;

		for (int i = 0; i < k; i++) {
			char command; int value;
			cin >> command >> value;

			if (command == 'I') { // 삽입
				if (que.find(value) == que.end())
					que.insert({ value, 1 });
				else
					que[value]++;
			}
			else { // 삭제
				if (!que.empty()) {
					map<int, int, greater<int>>::iterator iter;
					if (value == 1)
						iter = que.begin(); // 최댓값
					else
						iter = --que.end(); // 최솟값

					if (--iter->second == 0) // count가 0이면 삭제
						que.erase(iter);
				}
			}
		}

		if (que.empty())
			cout << "EMPTY\n";
		else
			cout << que.begin()->first << " " << (--que.end())->first << "\n";
	}

	return 0;
}

간단하게 풀기는 했지만, 당연하다시피 속도가 매우 느렸다.

다른 사람의 코드를 보니 min-max heap이라는 자료구조가 나와 공부해봤는데, 신세계를 보았다.

Min-Max Heap: http://blog.naver.com/PostView.nhn?blogId=heojh93&logNo=220020760884

Min-Max Heap을 구현하고 문제를 풀어보자.

1. SEH (Structured Exception Handling)

• SEH는 Windows OS에서 지원하는 예외처리 방식으로 __try, __except, __finally 문법으로 이루어진다. 안티디버깅 용도로도 사용된다.
• __try 블록 내에서 예외가 발생하면 __except 문에 해당되는 예외 핸들러(Exception Handler)를 호출하여 예외를 처리한다.
• __except 블록 안에서 GetExceptionCode 함수를 이용해서 예외 종류를 확인하고 세 가지 선택(exception filter)을 할 수 있다. __except 문의 예외 핸들러 실행 (EXCEPTION_CONTINUE_EXECUTION), 예외의 원인을 해결하고 예외 발생한 곳에서 이어서 실행, 다음 예외 핸들러 찾기 (EXCEPTION _CONTINUE_SEARCH)
• __try 영역 밖을 벗어나게 되면 __finally 영역 내의 코드(Termination Handler)를 실행한다. 스레드 강제 종료, 프로세스 종료를 제외한 모든 제어문(return, break 등)을 통해 영역 밖을 나갈 때도 실행된다.

2. VEH (Vectored Exception Handler)

• VEH는 SEH를 응용프로그램 범위로 확장한 것으로 프로그램에서 예외가 발생하면 제일 먼저 호출된다. AddVectoredExceptionHandler라는 함수로 추가 할 수 있다.

3. VCH (Vectored Continue Handler)

•  VCH는 VEH와 SEH에서 EXCEPTION_CONTINUE_EXECUTE가 반환되었을 때 호출 된다.

4. UEH (Unhandled Exception Handler)

• UEH는 모든 예외 핸들러에서 처리되지 못한 예외를 처리하는 곳이다.

5. Unwind

• Local Unwind는 try-finally 구문에서 try 블록 내부에 return, goto 등의 제어문이 있을 때 발생한다. finally 블록을 실행 후 이동을 해야 하기 때문에 임시 변수를 생성해서 상태를 저장하는 것이다.
• Global Unwind는 예외 핸들러의 exception filter가 EXCEPTION_EXECUTE_HANDLER인 경우 발생하는데, try 블록 내부에서 예외가 발생하면 finally보다 except를 먼저 찾아 처리하기 때문에 예외를 처리하기 전에 제일 안에 있는 finally부터 처리해 except 블록까지 내려오는 행위다.