Programmers Level 0 - 겹치는 선분의 길이

문제 설명

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

입출력 예 설명

입출력 예 #1

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

입출력 예 #2

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

입출력 예 #3

• 첫 번째와 두 번째 선분이 [3, 5] 구간에서 겹칩니다.
• 첫 번째와 세 번째 선분 [1, 5] 구간에서 겹칩니다.
• 두 번째와 세 번째 선분 [3, 9] 구간에서 겹칩니다.
• 따라서 [1, 9] 구간에 두 개 이상의 선분이 겹쳐있으므로, 8을 return 합니다.

 

class Solution {
    public int solution(int[][] lines) {
        int answer = 0;
        int[] points = new int[200];
        // 모든 좌표를 다 연결하려고 선택정렬 알고리즘 사용
        for(int i=0;i<lines.length-1;i++) { 
            for(int j=i+1;j<lines.length;j++) {
                int x1 = Math.max(lines[i][0], lines[j][0]); // 시작 좌표의 최대값
                int x2 = Math.min(lines[i][1], lines[j][1]); // 종료 좌표의 최소값
                // 종료좌표의 최소값이 크다면 겹치는 부분이 존재한다.
                if(x2>x1) {
                    for(int k=x1;k<x2;k++) {
                        points[k + 100]++;
                    }
                }
            }
        }
        for(int n : points) {
            if(n>=1) answer++; 
        }
        return answer;
    }
}

 

-100 ≤ a < b ≤ 100 이므로 배열의 크기를 200으로 하였다.   배열을 반복하며 모든 좌표를 비교한다.  반복횟수를 줄이기 위해 선택정렬 알고리즌을 사용하였다.  두 선분의  x1좌표의 최대값과 x2좌표의 최소값을 구한다.    x2좌표의 최소값이 x1좌표의 최대값 보다 크다면 겹치는 부분이 있다.   반복문으로 그 좌표의 위치값이 있는 위치에 숫자를 증가시킨다.  음수는 배열의 첨자가 될 수 없으므로 -100일떄 +100을 하면 0이되도록 하여 표시한다.   마지막으로 배열 값이 0이 아닌 개수를 세면 겹치는 부분이 된다.

 

import java.util.HashMap;
import java.util.Map;
class Solution {
    public int solution(int[][] lines) {
        Map<Integer, Integer> map = new HashMap<>();
 
        for (int i=0; i<lines.length; i++) {
            for (int j=lines[i][0]; j<lines[i][1]; j++) {
                map.put(j, map.getOrDefault(j, 0) + 1);
            }
        }
        return (int) map.values().stream().filter(i -> i > 1).count();
    }
}

 

다른 풀이

맵을 만들어 좌표값의 위치를 모두 맵에 저장하는데 원래 값에 더하기 1을 해서 저장한다.   처음 저장할때  읽어올 값이 없으므로 get()으로 읽어오면 에러이므로 getOrDefault()로 읽어와 더하기 1을 한다.  1번 나온 좌표는 한번만 있는 좌표이고  두번 이상 나온 좌표는 겹치는 부분이므로 2이상인 개수를 세어주면 된다.