[Programmers] #120876 - 겹치는 선분의 길이 [Java][C++][Python]

문제 링크

---

1. 아이디어

여러 선분의 시작점과 끝점이 담긴 lines가 주어질 때, 두 개 이상의 선분이 겹치는 구간의 길이의 합을 구하는 문제로 좌표 범위가 -100 ~ 100으로 좁다는 점을 이용해 각 단위 구간마다 겹치는 선분의 개수를 센 다음 2개 이상 겹친 구간의 개수를 세면 그게 곧 정답이 된다.

좌표에 음수가 포함돼 배열 인덱스로 바로 쓸 수 없어서, 좌표에 100을 더한 값을 인덱스로 사용해 카운팅했다.

---

2. 복잡도

접근	시간	공간
풀이	$O(R)$	$O(R)$

($R$ = 좌표값이 가질 수 있는 범위, cnt 배열의 길이 201)

---

3. 코드

풀이 [Java][C++][Python]

class Solution {
    public int solution(int[][] lines) {
        int[] cnt = new int[100 + 1 + 100];
        for (int[] line : lines) {
            for (int i = line[0]; i < line[1]; i++) {
                cnt[i + 100]++;
            }
        }

        int ans = 0;
        for (int x : cnt) {
            if (x >= 2) ans++;
        }

        return ans;
    }
}

#include <bits/stdc++.h>
using namespace std;

int cnt[100 + 1 + 100];

int solution(vector<vector<int>> lines) {
    for (auto& line : lines) {
        for (int i = line[0]; i < line[1]; i++) {
            cnt[i + 100]++;
        }
    }

    int ans = 0;
    for (int x : cnt) {
        if (x >= 2) ans++;
    }

    return ans;
}

from collections import Counter


def solution(lines):
    cnt = Counter()

    for s, e in lines:
        for i in range(s, e):
            cnt[i] += 1

    return sum(v >= 2 for v in cnt.values())

Counter를 활용해서 각 선분마다 바로 카운팅했다.

---