[백준 22942] 데이터 체커

🔗 알고리즘 문제

이 문제는 지금까지 풀어왔던 자료구조 문제중 로직을 생각하기 가장 어려웠던 문제였다,,,
혼자서는 생각해내기 너무 어려운 문제여서 선생님의 도움을 받아 해결할 수 있었다.
앞으로는 이런 문제도 혼자서 풀 수 있게 열심히 해야겠다는 생각이 들었다.
또한 오랜만에 길게 생각하고 푼 문제라 어려웠지만 뿌듯했다.

문제 분석

이 문제는 간단히 말해 수직선에 그려져 있는 원이 서로 겹쳐있는지 아닌지 판단하면 되는 문제이다.

발상 및 알고리즘 설계

처음에는 두가지 방법으로 문제에 접근하였다.

1. 원의 정보를 순서대로 스택에 담고 하나씩 pop을 해가며 비교하는 방법
2. 모든 원의 정보를 반복문을 돌리며 하나하나 비교하는 방법

첫 번째 방법으로 접근할 경우 전체 값을 비교하는 것이 아닌 자신의 앞에 값하고만 비교하는 방식이기 때문에 문제가 생겼고, 두 번째 방법으로 접근할 경우 시간복잡도가 커지며 시간초과를 해결할 수 없었다.

이를 해결하기 위해 새로운 접근법을 찾아내었다.

수직선에 앞에 있는 순으로 원을 정렬한 후 반복을 돌리면 해당 원보다 앞에 있는 경우는 무시할 수 있으니

원이 기준 원의 안쪽에 있는 경우 / 원이 기준 원과 겹친 경우 / 원이 기준 원의 바깥쪽에 있는 경우

이 경우만 체크하면 된다.

기준 원의 안쪽에 있는 경우를 제외하고는 모두 원의 끝 점이 기준 원의 끝 점보다 바깥쪽에 있어야 하므로 그것을 먼저 구분한 후 원의 시작점의 위치를 통하여 겹쳐있는지 아닌지 확인하는 로직을 만들었다.

코드

#include<iostream>
#include<vector>
#include<algorithm>
#include<math.h>

using namespace std;

struct Circle
{
    int start;
    int end;
};

int main(){
    ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);

    vector<Circle> circles;

    int data_cnt;
    cin >> data_cnt;

    for(int i = 0; i < data_cnt; i++){
        int center, radius;
        cin >> center >> radius;

        circles.push_back({center - radius, center + radius});
    }

    sort(circles.begin(), circles.end(), [](Circle a, Circle b){
        return (a.end != b.end) ? a.start < b.start : a.end < b.end;
    });

    bool isOverlap = false;
    vector<int> end_stack;

    for(Circle circle : circles){
        while(!end_stack.empty() && end_stack.back() < circle.start){
            end_stack.pop_back();
        }

        if(!end_stack.empty() && circle.start <= end_stack.back() && end_stack.back() <= circle.end){
            isOverlap = true;
            break;
        }

        end_stack.push_back(circle.end);
    }

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