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

문제 힌트

1. 선분이 겹치는지 확인하는 조건을 파악하기
   • 두 선분 A와 B가 주어졌을 때, A와 B가 겹치는지 확인하려면 다음 조건을 만족해야 합니다:
     • A의 가장 오른쪽 위치가 B의 가장 왼쪽 위치보다 크고
     • A의 가장 왼쪽 위치가 B의 가장 오른쪽 위치보다 작아야 합니다.
   예시:
   • [-3, 0]와 [-1, 5]라는 선분이 있을 때, -1 ~ 0 구간에서 겹치는 것을 알 수 있습니다.
   • A의 가장 오른쪽 위치 0이 B의 가장 왼쪽 위치 -1보다 크고,
   • A의 가장 왼쪽 위치 -3이 B의 가장 오른쪽 위치 5보다 작습니다.
2. 데이터 구조 선택
   • 선분의 각 위치에서 겹치는 개수를 기록하기 위해 HashMap을 사용할 수 있습니다. HashMap은 키-값 쌍으로 데이터를 저장하며, 특정 위치에서 선분이 몇 개 겹치는지를 기록하기에 적합합니다.
   • 배열을 활용하여 imos법이라는 누적합으로 푸는 방법도 있습니다 궁금하시면 찾아보시는 것을 추천합니다
     정답에 추가로 imos법도 넣겠습니다
3. 구간 겹침 카운팅
   • 각 선분의 시작 위치부터 끝 위치까지 순회하며, 각 위치에서 선분이 몇 개 겹치는지를 HashMap에 기록합니다. 이렇게 하면 특정 위치에서 겹치는 선분의 개수를 쉽게 셀 수 있습니다.
   • 최종적으로 HashMap을 순회하며 두 개 이상의 선분이 겹치는 위치의 개수를 구합니다.

 

---

정답은 더보기 클릭

1. HashMap으로 풀기

import java.util.*;

// Solution 클래스 정의
class Solution {
    // 선분들이 겹치는 구간의 개수를 반환하는 메서드
    public int solution(int[][] lines) {
        // 각 위치에서 선분이 겹치는 개수를 저장할 HashMap
        HashMap<Integer, Integer> map = new HashMap<>();
        
        // 모든 선분을 순회
        for (int[] line : lines) {
            // 현재 선분의 시작 위치부터 끝 위치까지
            for (int i = line[0]; i < line[1]; i++) {
                // 현재 위치(i)에서 선분의 개수를 증가시킴
                // getOrDefault(i, 0) : 현재 위치 i에서 선분의 개수를 가져오고, 만약 위치 i가 HashMap에 없으면 0을 반환
                // +1 : 해당 위치에서 선분의 개수를 1 증가
                map.put(i, map.getOrDefault(i, 0) + 1);
            }
        }
        
        int result = 0;
        // HashMap의 모든 값(각 위치에서의 선분 개수)을 순회
        for (int n : map.values()) {
            // 두 개 이상의 선분이 겹치는 위치를 찾기
            if (n > 1) {
                result++;  // 겹치는 선분이 있는 위치의 개수를 카운트
            }
        }
        
        // 결과를 반환
        return result;
    }
}

 

2. imos법으로 풀기

class Solution {
    public int solution(int[][] lines) {
        // imos 배열을 선언. 배열 크기는 201로, 인덱스 -100 ~ 100을 표현하기 위해 사용
        int[] imos = new int[201];
        
        // 각 선분에 대해 imos 배열에 시작점과 끝점 표시
        for (int[] line : lines) {
            // 선분의 시작점에서 +1
            imos[line[0] + 100]++;
            // 선분의 끝점에서 -1
            imos[line[1] + 100]--;
        }
        
        // 누적합 계산. imos 배열의 각 위치에 대해 이전 값을 더함
        for (int i = 0; i < imos.length - 1; i++) {
            imos[i + 1] += imos[i];
        }
        
        int result = 0;
        
        // imos 배열을 순회하며 겹치는 구간의 개수를 셈
        for (int i = 0; i < imos.length; i++) {
            // 선분이 두 개 이상 겹치는 구간을 찾기
            if (imos[i] > 1) {
                result++;
            }
        }
        
        // 결과 반환
        return result;
    }
}