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

 

 

 

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

 

 

문제 3줄 요약

 

1. 원의 중심이 x축 위에 존재하는 원들이 존재 한다.

2. N개의 원들의 중심 x좌표와 반지름이 주어진다.

3. 각 원들이 서로 교점이 생기는지 않는지 확인해봐라.

 

---

 

문제에서 N의 최대 값이 200,000 으로

원을 하나 받을 때마다 그려진 원들을 전부 비교하기엔

N(N-1)/2 정도의 연산이 필요하니

대충 계산해봐도 200억 번의 연산이 필요하다.

 

 

따라서

원이 그려질 때마다 겹치는지 겹치지 않는지

범위 값을 담아두고 비교하는 형식이 필요할 것이다.

 

일단

원의 중심 좌표, 반지름을 통해

각 원의 최소 좌표와 최대 좌표를 vector에 담아 비교 연산에 필요한 값들을 세팅해주었다.

 

int n;
cin >> n;
vector<pair<int, int>> circles(n);

while(n--)
{
    int x, r;
    cin >> x >> r;

    circles[n] = make_pair(x-r, x+r);
}

 

구조체를 이용한 vector를 만들어 줄 수도 있지만,

pair로 값을 묶는게 더 익숙해서 int형 두 개를 묶은 pair를 사용하였다.

 

circles의 first와 second로 첫 번째, 두 번째 값을 대입해줄 수 있고

위와 같이 make_pair를 통해 한 줄에 두 값을 대입해 줄 수도 있다.

 

다음은 최소 좌표순으로 먼저 vector를 오름차순 정렬하고,

이후 최소 좌표가 같은 경우에는 최대 좌표를 오름차순으로 정렬하고자 한다.

 

Python에서는 lambda 식이 매우 간단하게 작성되었던 것 같았는데,

C++에서는 비교적 문법이 복잡하였다.

 

https://modoocode.com/196

씹어먹는 C++ 토막글 ② - 람다(lambda) 함수

 

위의 링크를 참고하여 작성하였으며,

천천히 살펴보겠다.

 

https://modoocode.com/196

 

람다식에는 위 그림과 같이 4개의 부분으로 나눠지는데

개시자, 인자, 반환 타입, 함수 구현부로 구성된다.

 

개시자는 함수 구현부 연산에서 외부 변수가 필요한 경우, 개시자에 담아서 구현부로 불러온다.

게시자는 []를 생략 불가능하다.

 

인자는 실행 시 받을 인자를 작성한다. 받을 인자가 없을 경우 생략 가능하다.

인자 옆에 반환 타입이 있는데 반환 타입이 void 인 경우에는 생략 가능하다.

 

따라서 위에서 하고자 했던 정렬을

아래와 같이 작성할 수 있을 것이다.

 

sort(circles.begin(), circles.end(), [](pair<int,int> left, pair<int,int> right) {
    return left.first != right.first ? left.first < right.first : left.second < right.second;
});

 

삼항 연산자를 이용하여

최소 좌표가 같은 경우에는 최대 좌표가 작은 값을 먼저 배치하며,

최소 좌표가 다른 경우에는 최소 좌표가 작은 값을 배치하여 오름차순 정렬해준다.

 

이젠 원들을 하나씩 그려줄 것이다.

그려진 원들의 최대 좌표를 담아주고 앞으로 그릴 원들과 비교할 것이므로

최대 좌표를 그려줄 vector를 생성 후 담아준다.

 

bool is_valid = true;
vector<int> end_stack;

// circles : {<1, 9, <2, 4>, <5, 7>, <10, 16>}
// circle : <1, 9>, end_stack : 9
// circle : <2, 4>, end_stack : 9, 4
// circle : <5, 7>, end_stack : 9, 7
// circle : <10, 16>, end_stack : 10

for(auto circle : circles)
{
    while(!end_stack.empty() && end_stack.back() < circle.first) // 비교할 우측 값만 남겨 놓기
    {
        end_stack.pop_back();
    }

    if(!end_stack.empty() && circle.first <= end_stack.back() && end_stack.back() <= circle.second) // 겹치는 경우
    {
        is_valid = false;
        break;
    }

    end_stack.push_back(circle.second);
}

 

 

그럼 계속 최대 좌표를 담아주기만 하는가?

 

그건 아니다.

 

오름차순 정렬을 했기에 반복문을 통해 원들을 받아 올 때,

받아오는 원들의 최소 좌표 또는 최대 좌표가 계속 커지게 될 것이다.

 

 

따라서 위의 그림처럼

받아온 원의 최소 좌표가 기존의 최대 좌표보다 큰 경우에는

이제 저 두 end point는 비교 대상에서 제외 될 것이다.

 

원을 x축의 좌측부터 우측으로 진행되며 그려지는 것이라 생각하면 되겠다.

 

 

 

만일 새로 그려줄 원의 최소 좌표가 end point 보다 같거나 작으며,

원의 최대 좌표가 end point 보다 크거나 같다면

새로 그려질 원이 end point의 원 안에 존재하는 것이 아닌

한 점 또는 두 점에 겹치는 원이게 된다.

 

겹치는 경우에는

is_valid를 false로 변경 후 반복문을 종료하게 된다.

이후 is_valid 값을 따라서 YES 와 NO의 출력을 나눠준다.

 

최종 코드는 아래와 같다.

 

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

using namespace std;

int main(void){
    ios::sync_with_stdio(0); // c stream, c++ stream 중 c++ stream만 사용
    cin.tie(0); // 버퍼 비우지 않음

    int n;
    cin >> n;
    vector<pair<int, int>> circles(n);

    while(n--)
    {
        int x, r;
        cin >> x >> r;

        circles[n] = make_pair(x-r, x+r);
    }

    sort(circles.begin(), circles.end(), [](pair<int,int> left, pair<int,int> right) {
        return left.first != right.first ? left.first < right.first : left.second < right.second;
    });

    bool is_valid = true;
    vector<int> end_stack;

    // circle : <1, 9>, end_stack : 9
    // circle : <2, 4>, end_stack : 9, 4
    // circle : <5, 7>, end_stack : 9, 7
    // circle : <10, 16>, end_stack : 10

    for(auto circle : circles)
    {
        while(!end_stack.empty() && end_stack.back() < circle.first) // 비교할 우측 값만 남겨 놓기
        {
            end_stack.pop_back();
        }

        if(!end_stack.empty() && circle.first <= end_stack.back() && end_stack.back() <= circle.second) // 겹치는 경우
        {
            is_valid = false;
            break;
        }

        end_stack.push_back(circle.second);
    }

    if (is_valid) {
        cout << "YES\n";
    } else {
        cout << "NO\n";
    }

    return 0;
}

 

---

 

풀이 방법이 딱 떠오르지 않으면..

시간 복잡도 고려하여 풀기엔 어려움이 있을 것 같다..!

 

이런 식의 접근도 있다라는 걸

눈에 익혀둬야겠다!

 

끝!