백준 : 22942 - 데이터 체커

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

 

앗 오늘도 수많은 삽질끝에,,,,,,

 

첨에는 냅다 완전탐색으로 풀었다.. 근데 역시나 20%에서 시간초과!!

근데 어떤 자료구조를 쓰라는건지...........했는데

정답은 stack이었다!

어짜피 x축위에 있으므로, 괄호처럼 보면 된다.

 

이렇게 왼쪽끝, 오른쪽끝을 각각 ()에 대입해보면 된다!

 

이러면,,,,, 진짜 그냥 맞는괄호찾기 문제가 된다

 

#include <iostream>
#include <vector>
#include <queue>
#include <stack>
using namespace std;

struct compare{
    bool operator()(vector<int> &a, vector<int> &b){
        return a[0] >= b[0];
    }
};

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

    int n;
    cin >> n;
    priority_queue<vector<int>, vector<vector<int>>, compare> myones; // {좌표, index, 0 (L) 1 (R)}
        for(int i = 0; i<n; i++){
        int x, r;
        cin >> x >> r;
        myones.push({x-r, i, 0});
        myones.push({x+r, i, 1});
    }

    
    stack<vector<int>> mystack;

    while(!myones.empty()){
        vector<int> nowin = myones.top();
        myones.pop();
        switch(nowin[2]){
            case 0:
                mystack.push(nowin);
                break;
            case 1:
                if(mystack.empty()){
                    cout << "NO";
                    return 0;
                }
                if(mystack.top()[2] == 0 && mystack.top()[1] == nowin[1]){
                    // 가능!
                    mystack.pop();
                    continue;
                }
                cout << "NO";
                return 0;
                break;
        }
    }

    if(mystack.empty()){
        cout << "YES";
    }else{
        cout << "NO";
    }
    

    return 0;
}

 

 

주의할점은 compare 비교조건인데.. 등호를 넣어줘야 통과한다!

이렇게 겹치는 부분은,,,, 잘못하면 검출이 안될 수 있다!

구현에 따라 두가지 경우가 나올 수 있고,,, 이걸 방지해줘야한다! 1번으로 들어가면 맞다고 해버리기 때문이다.

 

근데 저것도 좀 애매하긴하다.. 그냥 테스트케이스만 통과했지,,, 안될지두??