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

문제 설명

선분 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

---

입출력 예

lines	result
[[0, 1], [2, 5], [3, 9]]	2
[[-1, 1], [1, 3], [3, 9]]	0
[[0, 5], [3, 9], [1, 10]]	8

 

풀이

겹치는 선분의 길이를 더하고 중복으로 더해지는 구간을 빼야하나? 근데 이걸 어떻게 계산해야 하지?
이런 생각에 사로잡혀 다른 풀이는 생각도 못 하고 로직을 어떻게 짜야할지에만 집중하니 문제가 풀리지 않았다.
결국 도저히 모르겠어서 이런 저런 구글링을 했는데 “길이를 구한다”가 아닌 “선분이 지나가는 점을 찾는다” 가 정답이었다.
점의 범위가 -100~100이기 때문에 크기가 200인 배열을 만들고 선분에 포함되는 점은 값을 +1 해준다.
여러 번 지나가는 점은 당연히 값이 2 이상이 될 것이다.
그리고 마지막에 배열을 순회하며 값이 1보다 크면 answer++ 해서 return한다.
 
여기서 주의해야 할 점은 아래 정답 코드에서 for문 범위 설정이다.

for(int k=start; k<end; k++) {
                count[k] += 1;
            }

선분에 포함된 점을 체크할 때 end 까지 포함시킨다면 중간이 파여 있는 구간까지 계산이 되어버린다.
 
무슨 얘기인지 모르겠다면 아래 사진을 보자.

문제에서 그림으로 표현한 예제에서 선분 대신 지나가는 점만 체크한 건데 예제 상으로는 겹치는 구간이 [-2,-1], [0,1]로 길이는 2가 되어야 한다.
하지만 점으로 찍어보면 -2, -1, 0, 1 이렇게 4개의 점이 모두 값이 2로 되어서 answer = 4로 나온다.
 
여기서 만약 for문 범위를 end-1까지만 돌린다면

값이 2 이상인 점은 -2, 0 으로 answer = 2가 되는 것을 알 수 있다.

 

정답

class Solution {
    public int solution(int[][] lines) {
        int answer = 0;

        int[] count = new int[201];

        for(int[] i : lines) {
            int start = i[0]+100;
            int end = i[1]+100;

            for(int k=start; k<end; k++) {
                count[k] += 1;
            }
        }
        
        for(int i : count) {
            if(i>1) answer++;
        }

        return answer;
    }
}