백준 22942 데이터 체커

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

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

using namespace std;

vector<tuple<int, int, bool>> arr;

int main() {

    ios::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);

    int n;

    cin >> n;



    for (int i = 0; i < n; i++) {
        int x, r;
        cin >> x >> r;

        arr.push_back(make_tuple(x - r, i, true));
        arr.push_back(make_tuple(x + r, i, false));
    }

    sort(arr.begin(), arr.end());


    stack<int> st;
    for (int i = 0; i < arr.size(); i++) {
        if(get<2>(arr[i])) {
            st.push(get<1>(arr[i]));
        } else {
            if (st.top() != get<1>(arr[i])) {
                cout << "NO";
                return 0;
            } else {
                st.pop();
            }
        }
    }

    cout << "YES";

    return 0;
}

1. 문제

x 좌표에 원이 주어진다. n개의 원의 중심과 반지름이 각각 주어진다. 이 원들의 교점이 없으면 YES, 교점이 하나라도 있다면 NO를 출력하는 문제이다.

2. 풀이

  for (int i = 0; i < n; i++) {
        int x, r;
        cin >> x >> r;

        arr.push_back(make_tuple(x - r, i, true));
        arr.push_back(make_tuple(x + r, i, false));
    }

    sort(arr.begin(), arr.end());

 스택을 사용하여 풀기 위해 튜플로 벡터를 만들었다. 각각 원이 x좌표와 만나는 지점의 좌표, 원의 번호, 왼쪽 여부를 나타낸다. 왼쪽부터 하나씩 원을 그려가면서 확인하기 위해 배열을 정렬한다.

stack<int> st;
    for (int i = 0; i < arr.size(); i++) {
        if(get<2>(arr[i])) {
            st.push(get<1>(arr[i]));
        } else {
            if (st.top() != get<1>(arr[i])) {
                cout << "NO";
                return 0;
            } else {
                st.pop();
            }
        }
    }

 원의 왼쪽부분이면 스택을 추가한다. 닫는 부분인데 스택의 top과 원의 번호가 다르다면 다음과 같은 상황이 발생한다.

top의 원이 닫히지 않은 상태에서 arr을 닫으려 하면 무조건 교점이 생기므로 NO를 출력한다. 

이런 경우에는 arr이 열릴 때 top에 들어가고 다시 닫히게 되므로 교점이 생기지 않는다. 즉, 원이 열린 역순으로 닫으면 교점이 생기지 않는다. 그러므로 위 처럼 스택을 사용하여 풀 수 있다.

 

 연산이 끝날때 까지 교점이 생기지 않으면 YES를 출력한다.