Level 0. 겹치는 선분의 길이

Level 0. 겹치는 선분의 길이

 

 

각 선분이 지나는 점들의 값을 1씩 증가시켜 2 이상인 점의 개수를 찾아 해결했다.

 

값을 증가시키기 위해 순회하지 않고 범위를 이용해서 좀 더 효율적인 방법이 있나 찾아보았다.

 

겹치는 부분이 아니라 이어진 부분을 찾는 문제에서는 스위핑 기법 같은 것이 있었는데 이 문제에 대해서는 더 효율적인 방법을 찾을 수 없었다.

 

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

using namespace std;

int solution(vector<vector<int>> lines)
{
    vector<int> v(200, 0);

    for (vector<int>& line : lines)
        for (int i = line[0]; i < line[1]; ++i)
            ++v[100 + i];

    return count_if(v.begin(), v.end(), [](const int e) { return 1 < e; });
}

 

순차적으로 접근하는 for문이나 for_each() 함수 말고 성능을 위해 순차 접근을 보장하지 않는 transform() 함수를 사용하면 조금 더 빨리 수행할 수 있다.

 

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

using namespace std;

int solution(vector<vector<int>> lines)
{
    vector<int> v(200, 0);
    auto it_middle = v.begin() + 100;

    for (vector<int>& line : lines)
        transform(it_middle + line[0], it_middle + line[1], it_middle + line[0], [](const int e) { return e + 1; });

    return count_if(v.begin(), v.end(), [](const int e) { return 1 < e; });
}