[Codility] NumberOfDiscIntersections.cpp

코딜리티 Number of disc intersections 문제 링크

· 최초 아이디어

정렬을 활용하는 문제기 때문에 그 아이디어를 떠올려봤다. {거리, 인덱스}를 원소로 가지고 거리를 기준으로 대소를 비교하는 구조체를 만들고 set에 삽입해 정렬해주었다.

카운팅에 포함할지 여부를 결정하는 visit 배열을 만들고 set에서 가장 큰 반지름을 가지는 원부터 차례로 꺼내 visit이 false인 것들 중 범위 내에 몇 개의 원의 중심이 들어오는지 확인했다. 해당 지점에서의 intersections 카운팅이 끝나면 이후의 카운팅에 포함되면 안 되기 때문에 visit을 true 처리해주어 이후의 카운팅에서 제외되도록 하였다.

이를 모든 점에 대해 반복한다. 문제는 자꾸 테스트 케이스에 비해 실제로 카운팅되는 intersections이 부족했고, 일부 케이스에서 시간초과가 난 것이다.

#include <set>

struct Discs{
    int distance;
    int index;

    bool operator < (const Discs &data) const{
        if(distance == data.distance){
            return index > data.index;
        }
        else{
            return distance > data.distance;
        }
    }
};

int solution(vector<int> &A) {
    set<Discs> discs;  // {dist, idx}
    vector<bool> visit(A.size(), false);

    for(int index = 0; index < A.size(); index++){
        discs.insert({A[index], index});
    }

    int intersect = 0;
    for(auto iter = discs.begin(); iter != discs.end(); iter++){
        int index = (*iter).index;
        int distance = (*iter).distance;
        
        int start = 0;
        int end = A.size() - 1;
        if(index - distance > 0){
            start = index - distance;
        }
        if(index + distance < A.size()){
            end = index + distance;
        }
        
        int count = 0;
        for(int tmpIdx = start; tmpIdx <= end; tmpIdx++){
            if(tmpIdx == index)
                continue;
            if(!visit[tmpIdx]){
                count++;
            }
        }
        visit[index] = true;
        intersect += count;
    }

    if(intersect > 10000000){
        intersect = -1;
    }
    return intersect;
}

· 최종 아이디어

주어진 예시를 보았을 때, 각 디스크의 시작점(lower)과 끝점(upper)가 존재한다. 각 디스크에 대해서 해당 정보를 배열로 만들고 오름차순으로 정렬하였다.

이후 디스크가 닿는 가장 작은 좌표부터 차례로 탐색하면 새로운 디스크와 겹치는 지점(intersection)을 발견할 수 있다. intersection을 발견할 때마다 현재 몇 개의 디스크가 겹치는지 확인하여 카운팅해준다. 그리고 다음 겹치는 지점에 도달하기 전에 디스크를 벗어나는 지점이 있다면 겹치는 디스크 수에서 제외해준다.

#include <algorithm>

int solution(vector<int> &A) {
    vector<long long> lower;
    vector<long long> upper;

    long long intersect_cnt = 0;
    for(long long index = 0; index < A.size(); index++){
        lower.push_back(index - A[index]);
        upper.push_back(index + A[index]);
    }

    sort(lower.begin(), lower.end());
    sort(upper.begin(), upper.end());

    int upper_idx = 0;
    long long disc_cnt = 0;
    for(auto low : lower){
        while(upper[upper_idx] < low){
            upper_idx++;
            disc_cnt--;
        }
        intersect_cnt += disc_cnt;
        disc_cnt++;

        if(intersect_cnt > 10000000){
            return -1;
        }
    }
    return intersect_cnt;
}