[자바/+1-1] CodeTree. 구간 크기의 합

✨ 문제

코드트리 문제 링크

📈 해석

구간을 구분하는 유형은 +1 / -1 테크닉을 이용하여 풀 수 있다. 이 문제에서는 구간별 크기의 합을 묻고 있으므로, 모여있는 구간들을 하나의 연속된 구간으로 구분하여 그 크기를 계산하면 된다.

+1 / -1 테크닉을 사용하기 위해 입력되는 x의 값을 기준으로 정렬한다. 이 때, x좌표의 범위가 1 이상 10억 이하이므로 +1 / -1 값을저장하는건 모든 x에 대하여 배열 크기를 잡기보다는 좌표 개수만큼만 저장할 수 있도록 자료구조를 사용하면 된다. 나는 어차피 정렬+선입선출로 x를 사용해야 할 것으로 보여서 바로 우선순위큐를 이용하여 관리해 주었다. 이후 +1 / -1 값을 이용하여 0이 되는 지점을 체크하여 연속 구간을 구분하고, 구간이 시작되는 지점의 값을 int start에 저장한 뒤, 구간이 구분되는 시점에 이를 계산하여 int ans에 더해나가면 된다.

• 공식 해설과 논리적 차이는 없었다.

⏱ 시간복잡도

x값 기준으로 정렬한 뒤에 차례대로 보기 위해 우선순위 큐를 사용하였다. 이를 통해 n개의 점을 정렬하여 사용하므로 O(N * logN)만큼의 시간이 걸리며, n개의 점을 선형으로 순회하면서 연속 구간 구분 지점을 탐색하므로 O(N)만큼의 시간이 걸린다. 따라서 O(N * logN) 으로 문제를 풀 수 있다.

✔ 코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.PriorityQueue;
import java.util.Queue;
import java.util.StringTokenizer;
import java.util.stream.Stream;

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        Queue<Pair> pq = new PriorityQueue<>();

        int n = Integer.parseInt(br.readLine());


        for (int i = 0; i < n; i++) {
            int[] ab = Stream.of(br.readLine().split(" "))
                    .mapToInt(Integer::parseInt)
                    .toArray();
            int[] ap = new int[]{ab[0], 1};
            int[] bp = new int[]{ab[1], -1};

            Pair a = new Pair(ab[0], 1);
            Pair b = new Pair(ab[1], -1);
            pq.add(a);
            pq.add(b);
        }

        int res = 0;
        int ans = 0;
        int start = 0;
        while (!pq.isEmpty()) {
            Pair now = pq.poll();
            int x = now.x;
            int v = now.v;

            if (res == 0) {
                start = x;
            }
            res += v;
            if (res == 0) {
                ans += now.x - start;
            }
        }
        System.out.println(ans);
    }

    private static class Pair implements Comparable<Pair> {
        private int x, v;

        private Pair(int x, int v) {
            this.x = x;
            this.v = v;
        }

        public int compareTo(Pair p) {
            return this.x - p.x;
        }
    }
}