문제

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

나의 풀이

1. 리스트의 [0]번째 원소로 내림차순 정렬
2. 스택으로 저장하여 pop() 
3. pop() 한 값의 [1]번쨰 원소와 남은 배열의 [0]번째 원소를 비교하여 
   차이값을 answer에 더하기

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

        Arrays.sort(lines, (o1, o2) -> o2[0] - o1[0]);

        Stack<int[]> stacks = new Stack<>();

        for (int[] line : lines) {
            stacks.add(line);
        }

        while (!stacks.isEmpty()) {
            int[] arr = stacks.pop();

            for (int[] stack : stacks) {
                if (arr[1] > stack[0]) {
                    answer += (arr[1] - stack[0]);
                }
            }
        }

        return answer;
    }
}

• 위의 방식대로 구현했고 몇개는 통과했지만 아래와 같은 경우에는 2개 이상의 선분이 겹치는 구간이 서로 겹쳐 내가 구한 방식대로 값을 구하면 중복으로 계산되는 문제가 있었다.

lines = {{0, 5}, {1, 10}, {3, 9}}       0       5
  										  1           10
       										 3       9
     
# 예상 답 : 8 (1 - 9)    
# 내가 구한 풀이 답 : 13 (1-5, 3-5, 3-10)
								  9  <- 이부분도 9로 인식되어야하지만 10으로 인식		

다른 풀이

• 전체 범위 길이만큼의 배열을 생성 (-100 ~ 100)
• lines의 범위 만큼 배열의 값 ++
• 배열에서 값이 2이상인 곳의 합 구하기

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

        for (int[] line: lines) {
            for (int i = line[0]+100; i < line[1]+100; i++) {
                arr[i] += 1;
            }
        }

        for (int i = 0; i < 200; i++) {
            if (arr[i] >= 2) {
                answer++;
            }
        }

        return answer;
    }
}

• 나는 왜 생각하지 못했지