[프로그래머스][C++] 겹치는 선분의 길이

겹치는 선분의 길이

문제 링크

겹치는 선분의 길이

분석

3개의 선분이 주어집니다.
각 선분은 [start, end] 형태입니다.

시작점 a와 끝점 b가 주어집니다.

이 선분들이 겹치는 부분 중 최소 2개 이상이 겹치는 구간의 총 길이를 구해 반환하는 문제입니다.

풀이

#include <vector>

using namespace std;

int solution(vector<vector<int>> lines) {
    int answer = 0;
    
    // 각 구간별로 선분이 몇 개 지나가는지 카운트하여 저장하는 배열
    // 좌표 범위가 -100부터 100까지 가능하므로, -100을 0으로 가정하고 200까지 매핑
    vector<int> count(200, 0);
    
    // 모든 선분 순회
    for (int i = 0; i < lines.size(); ++i)
    {
        // 선분의 시작점부터 끝점 이전까지 반복
        for (int j = lines[i][0]; j < lines[i][1]; ++j)
        {
            // 음수 값을 배열 인덱스로 사용하기 위해서 +100을 더해 보정
            // 1을 더해 선분이 하나 더 지남을 표시
            count[j + 100] += 1;
        }
    }
    
    // 각 구간에서 겹친 선분 수가 2개 이상일 경우 겹치는 부분
    for (int i = 0; i < count.size(); ++i)
    {
        if (count[i] >= 2)
        {
            ++answer;
        }
    }
    
    return answer;
}

성능 요약

시간 복잡도는 $O(l)$입니다.

• 모든 선분을 순회하는 중첩 반복문 $O(n \times l)$
  • l은 각 선분의 총 길이
• 겹친 선분의 수를 세는 반복문 $O(201) \approx O(1)$
• $O(n \times l) + $O(1)$

공간 복잡도는 고정된 크기의 상수 공간을 사용하기 때문에 $O(1)$입니다.

• 각 구간별로 선분이 몇 개 지나가는지 카운트하여 저장하는 배열 $O(201) \approx O(1)$

테스트 성능

테스트 1 〉 통과 (0.01ms, 3.7MB)
테스트 2 〉 통과 (0.01ms, 4.14MB)
테스트 3 〉 통과 (0.01ms, 4.12MB)
테스트 4 〉 통과 (0.01ms, 4.2MB)
테스트 5 〉 통과 (0.01ms, 4.19MB)
테스트 6 〉 통과 (0.01ms, 4.2MB)
테스트 7 〉 통과 (0.01ms, 3.62MB)
테스트 8 〉 통과 (0.01ms, 4.15MB)
테스트 9 〉 통과 (0.01ms, 4.2MB)
테스트 10 〉 통과 (0.01ms, 4.2MB)