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

문제 설명

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

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

!https://grepp-programmers.s3.ap-northeast-2.amazonaws.com/files/production/e4122d8b-9ce2-49ce-a360-3d1284babd8a/line_2.png

선분이 두 개 이상 겹친 곳은 [-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

---

입출력 예 설명

입출력 예 #1

• 두 번째, 세 번째 선분 [2, 5], [3, 9]가 [3, 5] 구간에 겹쳐있으므로 2를 return 합니다.

입출력 예 #2

• 겹친 선분이 없으므로 0을 return 합니다.

입출력 예 #3

• 첫 번째와 두 번째 선분이 [3, 5] 구간에서 겹칩니다.
• 첫 번째와 세 번째 선분 [1, 5] 구간에서 겹칩니다.
• 두 번째와 세 번째 선분 [3, 9] 구간에서 겹칩니다.

---

아이디어

일단 선분은 3개만 주어지니까 첫번째 선분과 두번째 선분을 먼저 비교하고, 두번째 선분과 세번째 선분을 비교하고, 첫번째 선분과 세번째 선분을 비교해면 된다고 생각했다.

근데 여기서,,!

선분 3개가 모두 겹치는 경우도 있을 때를 고려해야 한다.

그래서 추가적으로 선분 3개가 겹칠때도 확인하면 될 것 같다.

첫번째 시도

class Solution {
    public int solution(int[][] lines) {
        int answer = 0;
        int all = 0; // 선분 3개 다 겹치는 경우 빼줘야 할 값
        
        // 절대값 빼도 되는데.. 지우기 귀찮아서 걍 냅둠
        if (lines[0][1] > lines[1][0]) answer += Math.abs(lines[0][1] - lines[1][0]);
        if (lines[1][1] > lines[0][0]) answer += Math.abs(lines[1][1] - lines[0][0]);
        if (lines[0][1] > lines[2][0]) answer += Math.abs(lines[0][1] - lines[2][0]);
        if (lines[2][1] > lines[0][0]) answer += Math.abs(lines[2][1] - lines[0][0]);
        if (lines[2][1] > lines[1][0]) answer += Math.abs(lines[2][1] - lines[1][0]);
        if (lines[1][1] > lines[2][0]) answer += Math.abs(lines[1][1] - lines[2][0]);
        
        // 선분 3개 모두 겹치는 경우
        if (lines[0][1]>lines[1][0] && lines[1][1]>lines[2][0] && lines[0][1]>lines[2][0])
            all = lines[0][1] - lines[1][0];
        else if (lines[1][1]>lines[2][0] && (lines[2][1]>lines[0][0] || lines[0][1]>lines[2][0]))
            all = lines[1][1] - lines[2][0];
        else if (lines[2][1]>lines[0][0] && (lines[0][1]>lines[1][0] || lines[1][1]>lines[0][0]))
            all = lines[2][1] - lines[0][0];

            
        return answer-all;
    }
}

실패 생각해보니 선분이 항상 0 1 2 순서대로 나열되어있는 것이 아니다. 그리고 이렇게 하면 고려해야 할 경우가 너무 많아서 다른 접근법을 시도해보기로 했다.

제한사항에서 [-100,100], 그리고 정수로만 표현되므로 이걸 이용해보려고 한다.

그렇다면 for문으로 -100부터 100까지 살펴보면서 두개 이상의 선분이 해당 점에 위치해 있을때 answer을 +1 해주면 될 것 같다.

일단 선분 범위인 200만큼의 배열을 만들고, 중첩 for문을 활용하여 선분의 길이를 추가해주었다. 그리고 이 배열이 1보다 큰 경우 answer을 1씩 추가하는 방식이다.

---

문제 풀이

class Solution {
    public int solution(int[][] lines) {
        int answer = 0;
        int[] range = new int[201]; //전체 선분 범위 설정
        
        for (int i=0;i<lines.length;i++) {
            for (int j=lines[i][0]+100;j<lines[i][1]+100;j++) {//-100부터 100까지의 범위를 0부터 200으로
                range[j]++;
            }
        } 
        
        for (int k=0;k<range.length;k++) {
            if (range[k]>1) answer++; 
    }
        return answer;
    }
}

+4