[프로그래머스][Lv.0][Java] 겹치는 선분의 길이

문제

https://school.programmers.co.kr/learn/courses/30/lessons/120876

프로그래머스

문제 설명

선분 3개가 평행하게 놓여 있습니다. 세 선분의 시작과 끝 좌표가 [[start, end], [start, end], [start, end]] 형태로 들어있는 2차원 배열 lines가 매개변수로 주어질 때, 두 개 이상의 선분이 겹치는 부분의 길이를 return 하도록 solution 함수를 완성해보세요.

lines가 [[0, 2], [-3, -1], [-2, 1]]일 때 그림으로 나타내면 다음과 같습니다.

선분이 두 개 이상 겹친 곳은 [-2, -1], [0, 1]로 길이 2만큼 겹쳐있습니다.

 

제한사항

• lines의 길이 = 3
• lines의 원소의 길이 = 2
• 모든 선분은 길이가 1 이상입니다.
• lines의 원소는 [a, b] 형태이며, a, b는 각각 선분의 양 끝점 입니다.
  • -100 ≤ a < b ≤ 100

 

풀이

1. 시작점은 1, 끝점은 -1로 표시하여 리스트에 추가한다. 이렇게 하면 선분이 시작할 때마다 선분의 개수를 증가시키고, 선분이 끝날 때마다 선분의 개수를 감소시킬 수 있다.
2. 위 리스트를 시작점을 기준으로 오름차순 정렬하되, 같은 시작점이 있을 경우 끝점이 먼저 오도록 정렬한다.
3. 각 점을 방문하면서 다음을 수행한다.
   • 선분의 개수가 2개 이상이면 현재 점과 이전 점 사이의 거리를 더한다.
   • 현재 점이 선분의 시작점이면 선분의 개수를 증가시킨다.
   • 현재 점이 선분의 끝점이면 선분의 개수를 감소시킨다.
   • 만약 선분의 개수가 2개 이상이면 prevPoint를 현재 점으로 설정한다.
   • 만약 선분의 개수가 2개 미만이고, 현재 점이 선분의 끝점이라면 prevPoint를 현재 점의 다음 점으로 설정하여 겹치지 않는 구간을 건너뛰도록 한다.

import java.util.*;

class Solution {
    public int solution(int[][] lines) {
        int answer = 0;
        List<int[]> points = new ArrayList<>();
        
        for (int[] line : lines) {
            points.add(new int[]{line[0], 1});
            points.add(new int[]{line[1], -1});
        }
        
        Collections.sort(points, (a, b) -> a[0] != b[0] ? a[0] - b[0] : b[1] - a[1]);
        
        int count = 0;
        int prevPoint = points.get(0)[0];
        
        for (int[] point : points) {
            if (count >= 2) {
                answer += point[0] - prevPoint;
            }
            if (point[1] == 1) {
                count++;
            } else {
                count--;
            }
            if (count >= 2) {
                prevPoint = point[0];
            } else if (point[1] == -1) {
                prevPoint = point[0] + 1;
            }
        }
        
        return answer;
    }
}