[boj : 20292] 컨설팅

www.acmicpc.net/problem/20292

20292번: 컨설팅

문제 : 지문에 써저있는 조건에 맞게 wait를 추가하여 출력하게끔 해라.

 

해설 : 최대 입력 문장이 10000 인 걸 고려해서 O(n^2)은 불안하여 O(nlogn) 의 시간 복잡도를 이용하여 문제를 해결하였습니다. 더불어 C++ 언어를 사용하시는 분께선 반드시 fastio를 사용해주세요. (요즘엔 선택이 아닌 필수라고 하더라구요)

 

소스:

#include<bits/stdc++.h>

using namespace std;

struct info {
	int x;
	string a, b;
	bool operator<(const info& cur) const {
		return x < cur.x;
	}
};

multiset<info> s;

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

	string input;
	while (true) {
		string x, y, z;
		cin >> input;
		if (input == "EXIT")break;
		if (input == "WRITE") {
			cin >> x >> y >> z;
			if (s.size() == 0) {
				cout << input << " " << x << " " << y << " " << z << "\n";
				s.insert({ 1,x,z });
			}
			else {
				bool flag = true;
				for (auto st = s.begin(); st != s.end(); st++) {
					if (st->x == 0 && st->a == z) {
						cout << "WAIT\n";
						s.clear();
						s.insert({ 1,x,z });
						cout << input << " " << x << " " << y << " " << z << "\n";
						flag = false;
						break;
					}
					else if(st->x==1 && (st->b==x || st->a==z || st->b==z || (st->a==x && st->b==z))){
						cout << "WAIT\n";
						s.clear();
						s.insert({ 1,x,z});
						cout << input << " " << x << " " << y << " " << z << "\n";
						flag = false;
						break;
					}
				}
				if (flag) {
					cout << input << " " << x << " " << y << " " << z << "\n";
					s.insert({ 1,x,z });
				}
			}
		}
		else {
			cin >> x;
			if (s.size() == 0) {
				cout << input << " " << x << "\n";
				s.insert({ 0,x });
			}
			else {
				bool flag = true;
				for (auto st = s.begin(); st != s.end(); st++) {
					if (st->x == 1 && st->b == x) {
						cout << "WAIT\n";
						s.clear();
						s.insert({ 0,x });
						cout << input << " " << x << "\n";
						flag = false;
						break;
					}
				}
				if (flag) {
					cout << input << " " << x << "\n";
					s.insert({ 0,x });
				}
			}
		}
	}
	cout << "EXIT";
	return 0;
}