[자바] 프로그래머스 - 겹치는 선분의 길이 (Lv0, Java)

문제 : Programmers-겹치는 선분의 길이

문제 출처: 프로그래머스 코딩 테스트 연습, https://programmers.co.kr/learn/challenges

 

필요 알고리즘 개념

• 구현
  • if문을 통해 세 선분을 비교해도 풀 수 있으나, 아이디어만 잘 세우면 그냥 배열에 카운팅만 해서 구현해주면 된다.

 

풀이

  선분의 수치는 -100~100 이다. 수치를 +100씩 해준다면 0~200 범위가 된다. 따라서 배열에 해당 선분이 차지하는 범위만큼 카운팅을 해줄 수 있다. 예를들어 아래와 같이 카운팅을 해줄 경우, 배열의 수치가 2 또는 3인 부분이 '두 개 이상의 선분이 겹치는 부분'이다. 

 

주의점은 그냥 [a, b] 범위에 대해 카운팅하는건 점에 대한 카운팅이다. 이 문제에서는 겹치는 면을 찾아야하므로, [a, b) 범위를 카운팅 해야 한다. 이하 이미지에서 위쪽 파란색 배열은 점에 대한 카운팅에 해당하며 이 경우 '4'가 답이 되어 틀리게 된다. 녹색 부분이 면에 대한 카운팅이다. 즉, 배열 arr[x]는 x~x+1 범위를 선분이 차지하고 있는 것으로 정의하면 된다.

 

 

코드 : github

/**
 * 문제 출처: 프로그래머스 코딩 테스트 연습, https://programmers.co.kr/learn/challenges
 */
class Solution {
    public int solution(int[][] lines) {
        int[] arr = new int[201];
        int answer = 0;
        for (int[] line : lines) {
            int a = line[0] + 100;
            int b = line[1] + 100;
            while (a<=b) {
                if (++arr[a++] == 2) answer++;
            }
        }
        return answer;
    }
}