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

프로그래머스

 

 

 

이해하기

처음에는 lines를 앞에서부터 하나씩 가져온 후, 이를 나머지 lines과 비교하여 겹치는 영역을 더하도록 하였다.

하지만 세번째 예시인 {{0, 5}, {3, 9}, {1, 10}}가 실패하였다.

이 때의 풀이는 각각의 0번 인덱스를 기준으로 정렬한 후, 서로 겹치는 부분을 answer에 더해주었다.

 

생각해보니 문제를 잘못 이해한 것이었다.

문제에서 요구한 것은 세 선분이 전부 겹친다면 위와 같이 셋의 겹치는 부분을 찾으라는 것이었다.

위 그림을 보면 1부터 9까지는 점이 2개 이상이고, 그렇기에 결과가 8이 되는 것이다.

 

참고한 블로그⬇️

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

 

하지만 주의해야 할 점이 있다.

문제에 나왔던 예시 중 {{0, 2}, {-3, -1}, {-2, 1}}의 그림은 아래와 같다.

 

겹치는 부분은 -2부터 -1까지 1만큼, 0부터 1까지 1만큼이라 답은 2가 되어야 한다.

하지만 이를 점으로 찍으면 아래와 같다.

단순히 점이 2개 이상일 경우를 세면 결과값은 4가 되게 되는 것이다.

문제점은 한 선분의 시작점과 다른 선분의 끝점이 겹칠 때이다. 그렇기에 끝점을 제외하고 점을 찍어야 한다.

끝점을 제외한 그림에서 점이 2개 이상일 경우를 세면 -2, 0으로 결과값이 2가 되게 된다.

 

 

문제풀이

import java.util.*;
import java.util.Map.*;

class Solution {
    public int solution(int[][] lines) {
        int answer = 0;
        
        Map<Integer, Integer> map = new HashMap<>();
        
        for (int i = 0; i < lines.length; i++) {
            int tempStart = lines[i][0];
            int tempEnd = lines[i][1];
            
            for (int j = tempStart; j < tempEnd; j++) {
                map.put(j, map.getOrDefault(j, 0) + 1);
            }
        }
        
        for (Entry<Integer, Integer> entry : map.entrySet()) {
            if (entry.getValue() >= 2) {
                answer++;
            }
        }
        
        return answer;
    }
}