[C++] 백준 22942번 : 데이터 체커

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

22942번: 데이터 체커

---

 문제 풀이

스택으로 구현한 문제이다!

원의 중심이 x선 상에 위치해 있다는 점을 통해서 괄호를 떠올렸다.

벡터에 (좌표, 열려있는지 여부, 순서) 를 저장하게 하는데 왼쪽 좌표와 오른쪽 좌표를 따로 받아

괄호의 열린 괄호, 닫힌 괄호를 구현했다. 

그리곤 정렬을 해준다. 

정렬 이후 위치값이 같은걸 우선적으로 찾아준다. 

앞서 위치값이 같은 게 있는지 확인했고 정렬을 했기 때문에 순서가 다른 게 온다면 false를 리턴하면 된다.

 느낀 점

처음에 아이디어 자체는 금방 떠올렸다. 근데 정렬을 하는 이유와 어떻게 구현할지를 조금 어려워했던 것 같다. 재밌던 문제였고 좋은 문제였다.

 코드

#include <iostream>
#include <stack>
#include <algorithm>
#include <vector>

using namespace std;

struct info { int pos, is_open, idx; };

int n, x, r;
vector<info> v;
stack<int> s;

bool compare(const info& a, const info& b) {
	return a.pos < b.pos;
}

bool solution() {
	for (int i = 1; i < v.size(); i++)
		if (v[i - 1].pos == v[i].pos) return 0;
	for (int i = 0; i < v.size(); i++) {
		if (v[i].is_open) s.push(v[i].idx);
		else if (v[i].idx == s.top()) s.pop();
		else return 0;
	}
	return 1;
}

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

	cin >> n;
	for (int i = 0; i < n; i++) {
		cin >> x >> r;
		v.push_back({ x - r, 1, i });
		v.push_back({ x + r, 0, i });
	}

	sort(v.begin(), v.end(), compare);

	cout << (solution() ? "YES" : "NO");
}