[BOJ] 데이터 체커 22942번 C++

 

 

문제

원 이동하기 2 문제를 만들고 만든 데이터가 문제의 조건에 맞는지 확인하는 코드를 작성해야한다.

해당 문제의 데이터는 아래 조건들을 만족해야한다.

1. 모든 원의 중심 좌표는 x축 위에 존재해야 한다.
2.  N개의 원 중 임의의 두 원을 선택했을 때, 교점이 존재하지 않아야 한다. 즉, 하나의 원이 다른 원 안에 존재하거나 외부에 존재한다.

데이터 형식은 원의 개수 N이랑 각 원의 중심 x좌표, 원의 반지름 r만 주어진다. 따라서, 2번 조건을 만족하는지만 확인하면 된다.

주어진 데이터가 해당 조건을 만족하는지 확인해보자.

입력

첫 번째 줄에는 원의 개수 N이 주어진다.

두 번째 줄부터 N+1번째 줄까지 원의 중심 x좌표, 원의 반지름 r이 공백으로 구분되어 주어진다.

 

출력

데이터가 조건에 맞는다면 YES, 조건에 만족하지 않는다면 NO를 출력한다.

 

접근 방식

 

문제 분류가 자료 구조라 어떤 식으로 접근해야 할지 꽤나 고민했다

가장 간단한 방법은 원의 좌표 순으로 정렬 후 두개의 원이 맞닿아 있는지를 비교하면 되는데

이는 자료 구조를 전혀 이용하지 않는 풀이였다.

 

고민해보다가 현재는 원의 x 좌표만 이용해서 풀이하면 되므로

원의 시작 x  좌표와 종료 x 좌표를 이용하면 되겠다고 생각이 들었다

벡터에 원의 종류(인덱스 번호), 좌표(시작 or 종료 좌표)를 넣고 정렬해 주었다

 

그리고 stack을 이용해 원의 시작 좌표를 가지고 있고 종료 좌표를 만났을 때 pop해주고

그렇지 않다면 push 해주었다.

 

만약 원이 다른 원과 만나면 stack 남아있을 것이고 그렇지 않다면 stack에서 모두 pop 될 것이다.

이를 활용해 마지막에 stack이 비어있으면 YES를 비어있지 않다면 NO를 출력해주었다.

 

생각보다 코드는 간단한데 문제 풀이 방식이 잘 생각나지 않았던 문제였다

 

 

코드

#include<bits/stdc++.h>
using namespace std;

int N;
vector<pair<int,int>> coordinates; // 원의 시작, 종료 좌표

bool comp(const pair<int,int>& a, const pair<int,int> &b) {
    if(a.first == b.first) return a.second < b.second;
    return a.first < b.first;
}

int main() {
    cin>>N;
    for(int i=0; i<N; i++) {
        int x, r; cin>>x>>r;
        coordinates.push_back({x-r, i});
        coordinates.push_back({x+r, i});
    }
    sort(coordinates.begin(), coordinates.end(),comp);

    stack<pair<int,int>> st;

    for(int i=0; i<coordinates.size(); i++) {
        if(!st.empty() && st.top().second == coordinates[i].second) st.pop();
        else st.push({coordinates[i].first, coordinates[i].second});
    }

    if(st.empty()) cout<<"YES";
    else cout<<"NO"; 

}