예제로 배우는 알고리즘 - 구간

구간 병합

 

예제 - LeetCode 228. Summary Range

https://leetcode.com/problems/summary-ranges/description/?envType=study-plan-v2&envId=top-interview-150

 

1. 문제 이해

• 주어진 배열에서 연속된 부분을 a->b 또는 a로 압축하여 표현

 

2. 요구사항 분석

• 입력
  • 0 <= nums.length <= 20
  • nums[i]는 int 범위
  • nums는 오름차순으로 정렬되어 있으며 nums[i]는 중복 없음
• 출력
  • 압축한 String 리스트

 

 

3. 해결 아이디어

• 연속 구간의 시작점을 설정
• 배열을 순회하며 이전 값과 현재 값을 비교 -> 다르면 연속 구간의 마지막
• 시작점과 마지막을 비교하여 구간이 1개인지 여러개인지 확인 -> 주어진 형식으로 리스트에 추가
• 마지막 구간을 동일하게 처리

 

4. 시간 복잡도 및 공간 복잡도 확인

 

• 시간 복잡도
  • 배열을 한번만 순회하므로 O(n)
• 공간 복잡도
  • 결과를 저장할 리스트가 필요하므로 O(n)

 

5. 구현

class Solution {
    public List<String> summaryRanges(int[] nums) {
        // 1. 결과 리스트 할당
        List<String> result = new ArrayList<>();
        int n = nums.length;

        // nums의 길이가 0이면 빈 리스트 반환
        if (n == 0) return result;

        int start = nums[0]; // 현재 범위 시작점

        // 2. 배열을 순회하며 연속된 부분 탐색
        for (int i = 1; i < n; i++) {
            // 2-1) 연속이 끊기면 범위 기록 후 시작점 갱신
            if (nums[i] != nums[i - 1] + 1) {
                // 시작점이랑 이전 값이 같음 : 연속된 부분이 1개
                if (start == nums[i - 1]) {
                    result.add(String.valueOf(start));
                // 시작점이랑 이전 값이 다름 : 연속된 부분이 여러개, 이전 값이 연속의 마지막
                } else {
                    StringBuilder sb = new StringBuilder();
                    sb.append(start).append("->").append(nums[i - 1]);
                    result.add(sb.toString());
                }
                start = nums[i]; // 새로운 범위 시작
            }
        }

        // 3. 마지막 범위 추가
        if (start == nums[n - 1]) {
            result.add(String.valueOf(start));
        } else {
            StringBuilder sb = new StringBuilder();
            sb.append(start).append("->").append(nums[n - 1]);
            result.add(sb.toString());
        }

        return result;
    }
}

 

예제 - LeetCode 56. Merge Intervals

https://leetcode.com/problems/merge-intervals/description/?envType=study-plan-v2&envId=top-interview-150

 

1. 문제 이해

• 주어진 구간들 중 겹치는 부분을 병합하여 겹치지 않는 구간들의 배열을 반환

 

2. 요구사항 분석

• 입력
  • 1 <= intervals.length <= 10,000
  • intervals[i].length = 2
  • 0 <= start <= end <= 10,000
• 출력
  • 겹치지 않는 구간들의 배열

 

 

3. 해결 아이디어

• 각 구간의 시작 지점을 인덱스로, 최대 도착 지점을 값으로 하는 배열 만들기 -> 정렬을 사용 안하므로 시간 복잡도에 이점이 있음
• 위의 배열을 순회하며 최대 도달 지점 갱신
• 최대 도달 지점과 현재 위치가 같다면 구간의 끝이므로 구간을 추가하고 구간 시작 및 최대 도달 지점 초기화

 

4. 시간 복잡도 및 공간 복잡도 확인

 

• 시간 복잡도
  • 입력 배열(n)을 2번 최대 도달거리 배열(k)을 1번 순회하므로 O(n + k)
• 공간 복잡도
  • 결과 리스트 (n)및 최대 도달 배열(k)을 사용하므로 O(n + k)

 

5. 구현

class Solution {
    public int[][] merge(int[][] intervals) {
        // 1. 시작점 중 최대값 계산 -> 시작점을 기준으로 끝점을 기록할 배열을 사용하기 위함
        int maxStartPoint = 0;
        for (int[] interval : intervals) {
            maxStartPoint = Math.max(maxStartPoint, interval[0]);
        }

        // 2. 시작 위치별로 가장 멀리 갈 수 있는 끝 지점을 기록
        int[] maxReach = new int[maxStartPoint + 1];
        for (int[] interval : intervals) {
            int start = interval[0];
            int end = interval[1];
            // 도착 지점이 0인 경우 계산의 용이를 위해 기준점을 0이 아닌 1로 수정 -> 이후 계산 시 도착 지점 -1 해주기
            maxReach[start] = Math.max(maxReach[start], end + 1);
        }

        // 3. maxReach를 순회하며 겹치는 구간을 합병
        List<int[]> mergedIntervals = new ArrayList<>();
        int currentIntervalStart = -1;
        int furthestEnd = -1;

        for (int position = 0; position < maxReach.length; position++) {
            // 3-1) 구간이 존재할 경우
            if (maxReach[position] != 0) {
                // 구간 시작이 안됐으면 현재 인덱스를 시작점으로 사용
                if (currentIntervalStart == -1) {
                    currentIntervalStart = position;
                }
                // 가장 멀리 갈 수 있는 구간 갱신
                furthestEnd = Math.max(furthestEnd, maxReach[position] - 1);
            }

            // 현재 위치(인덱스)가 최대 도달 거리이면 구간 추가
            if (position == furthestEnd) {
                mergedIntervals.add(new int[]{currentIntervalStart, furthestEnd});
                currentIntervalStart = -1;
                furthestEnd = -1;
            }
        }

        // 4. 아직 구간이 남았다면 마지막 구간 처리
        if (currentIntervalStart != -1) {
            mergedIntervals.add(new int[]{currentIntervalStart, furthestEnd});
        }

        // 5. 결과 리스트를 활용하여 2차원 배열로 변환
        return mergedIntervals.toArray(new int[mergedIntervals.size()][]);
    }
}

 

예제 - LeetCode 57. Insert Interval

https://leetcode.com/problems/insert-interval/description/?envType=study-plan-v2&envId=top-interview-150

 

1. 문제 이해

• 기존 오름차순으로 정렬된 구간에 새로운 구간을 삽입하여 정렬된 상태를 유지하면서도 중첩된 구간은 병합하여 반환

 

2. 요구사항 분석

• 입력
  • 1 <= intervals.length <= 10,000
  • intervals[i].length = 2
  • newInterval.lenght = 2
  • 0 <= start <= end <= 10,000
  • intervals는 start를 기준으로 오름차순 정렬
• 출력
  • 구간을 삽입한 후 배열

 

 

3. 해결 아이디어

• 새 구간을 기준으로 이전 구간들을 리스트에 추가
• 새 구간과 겹치는 구간들은 병합 후 리스트에 추가
• 새 구간을 기준으로 이후 구간들을 리스트에 추가

 

4. 시간 복잡도 및 공간 복잡도 확인

 

• 시간 복잡도
  • intervals를 한 번 순회하므로 O(n)
• 공간 복잡도
  • 결과 리스트를 사용하므로 O(n)

 

5. 구현

class Solution {
    public int[][] insert(int[][] intervals, int[] newInterval) {
        // 1. 결과를 저장할 배열 할당
        List<int[]> result = new ArrayList<>();
        int i = 0;
        int n = intervals.length;

        // 2. newInterval보다 앞에 있는 구간들을 결과에 추가
        while (i < n && intervals[i][1] < newInterval[0]) {
            result.add(intervals[i]);
            i++;
        }

        // 3. newInterval과 겹치는 구간들을 병합
        while (i < n && intervals[i][0] <= newInterval[1]) {
            newInterval[0] = Math.min(newInterval[0], intervals[i][0]);
            newInterval[1] = Math.max(newInterval[1], intervals[i][1]);
            i++;
        }
        result.add(newInterval);

        // 4. newInterval보다 뒤에 있는 구간들을 결과에 추가
        while (i < n) {
            result.add(intervals[i]);
            i++;
        }

        return result.toArray(new int[result.size()][]);
    }
}

 

예제 - LeetCode 452. Minimum Number of Arrows to Burst Ballons

https://leetcode.com/problems/minimum-number-of-arrows-to-burst-balloons/description/?envType=study-plan-v2&envId=top-interview-150

 

1. 문제 이해

• 가로 길이가 있는 여러 풍선들이 주어짐(y좌표는 알 수 없음)
• 특정 x 좌표를 선택해서 화살을 쏠 수 있음
• 모든 풍선을 터뜨릴 수 있는 최소의 화살 개수 구하기

 

2. 요구사항 분석

• 입력
  • 1 <= points.length <= 100,000
  • points[i].length = 2
  • start <= end
  • start와 end는 int 범위
• 출력
  • 최소 화살 개수

 

 

3. 해결 아이디어

• 풍선의 끝점을 기준으로 정렬
• 풍선들을 순회하며 이전 화살 발사 위치보다 현재 풍선의 시작점이 더 크다면 새로운 화살 필요
• 화살 갯수를 더해주고 발사 위치 갱신

 

4. 시간 복잡도 및 공간 복잡도 확인

 

• 시간 복잡도
  • 정렬(nlogn)과 순회(n)를 하므로(nlogn > n) O(nlogn)
• 공간 복잡도
  
  • 고정된 크기의 변수만 사용하므로 O(1)

5. 구현

class Solution {
    public int findMinArrowShots(int[][] points) {
        // 1. 끝점을 기준으로 정렬
        Arrays.sort(points, (a, b) -> Integer.compare(a[1], b[1]));

        int arrows = 1;
        int lastArrowPos = points[0][1];

        for (int i = 1; i < points.length; i++) {
            // 2. 현재 풍선이 이전 화살로 터질 수 없으면 새로운 화살 필요
            if (points[i][0] > lastArrowPos) {
                arrows++;
                lastArrowPos = points[i][1];
            }
        }

        return arrows;
    }
}

 

int 범위의 두 변수(start, end)를 사용하므로 long에 두 값을 담고 정렬을 하면

박싱/언박싱 비용, 기본형 비교, 캐시 효율성을 이유로 더 빠른 연산이 가능

 

class Solution {
    public int findMinArrowShots(int[][] points) {
        // 1. long 변수의 앞에는 end, 뒤에는 start 지점을 기록
        int n = points.length, idx = 0;
        long[] sort = new long[n];
        for(int[] point : points){
            sort[idx++] = (((long) point[1]) << 32) | (point[0] & 0xFFFFFFFFL);
        }

        // 2. 정렬(end 기준으로 됨) -> 박싱/언박싱, 기본형 비교, 캐시 효율성에 이점
        Arrays.sort(sort);

        // 3. end와 start를 비교하여 start가 더 크면 화살 갯수를 느리고 end 갱신
        int end = (int) (sort[0] >>> 32);
        int ans = 1;
        for(int i = 1; i < points.length; i++){
            // long을 int로 형변환 시 앞의 32자리가 사라짐 -> start
            if((int) sort[i] > end){
                ans++;
                end = (int) (sort[i] >>> 32);
            }
        }

        return ans;
    }
}