[백준] 1689번. 겹치는 선분(JAVA)

문제

https://www.acmicpc.net/problem/1689

---

풀이(15분)

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.PriorityQueue;
import java.util.StringTokenizer;

public class Main {

	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st;

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

		PriorityQueue<Point> pq = new PriorityQueue<>();
		for (int i = 0; i < N; i++) {
			st = new StringTokenizer(br.readLine());
			int s = Integer.parseInt(st.nextToken());
			int e = Integer.parseInt(st.nextToken());
			pq.add(new Point(true, s));
			pq.add(new Point(false, e));
		}

		int cnt = 0;
		int max = 0;
		while (!pq.isEmpty()) {
			Point p = pq.poll();
			if (!p.isStart) {
				cnt -= 1;
			} else {
				cnt += 1;
				max = Math.max(max, cnt);
			}
		}

		System.out.println(max);
	}

	static class Point implements Comparable<Point> {
		boolean isStart;
		int value;

		public Point(boolean isStart, int value) {
			this.isStart = isStart;
			this.value = value;
		}

		@Override
		public int compareTo(Point o) {
			if (this.value != o.value) {
				return this.value - o.value;
			}
			if (!this.isStart) { // 끝나는거 먼저 빼줘야함
				return 0;
			} else {
				return 1;
			}
		}
	}
}

---

문제 풀이 전략

 

🧩 문제 풀이 전략 — 구간합 개념으로 접근하기

이 문제는 구간합(prefix sum) 개념을 이용하면 아주 간단하게 해결할 수 있다.

 

💡 구간합이라고 하면 좀 어렵게 들릴 수도 있지만,

비유하자면 “길을 따라가며 돌을 줍고 놓는 문제”로 생각해볼 수 있다.

 

🪨 돌 줍기 비유로 풀어보기

1. 돌을 줍는 시점 = 구간의 시작점
2. 돌을 내려놓는 시점 = 구간의 끝점

우리는 길을 따라가면서,
각 지점에서 “돌을 몇 개 가지고 있는지”를 세면 된다.
이 값이 바로 “현재 시점에서 겹치는 구간의 개수”이고,
그 중 최댓값이 우리가 찾는 답(최대 겹침 수)이다.

 

🧠 예시로 생각해보기

구간	시작	끝
1	1	3
2	2	4
3	1	5
4	2	6
5	3	7
6	3	8

 

🚶 길을 따라가며 상황을 살펴보면

1️⃣ 1번 지점

• 1번, 3번 돌을 줍는다.
  👉 현재 가지고 있는 돌: 2개
  👉 구간 [1~2) 동안 돌 2개를 들고 감

2️⃣ 2번 지점

• 2번, 4번 돌을 줍는다.
  👉 현재 돌 4개
  👉 구간 [2~3) 동안 돌 4개를 들고 감

3️⃣ 3번 지점

• 1번 돌을 내려놓고, 5번과 6번 돌을 줍는다.
  👉 현재 돌 개수 변동: -1 +2 = +1 → 총 5개
  👉 구간 [3~4) 동안 돌 5개를 들고 감

이런 식으로 진행하면,
각 시점에서 현재 가지고 있는 돌의 개수(=누적합) 을 계산할 수 있고,
그 중 가장 많았던 순간의 값이 답이 된다.

 

⚙️ 코드로 표현하면

• 시작점에서 +1 (돌 줍기)
• 끝점에서 -1 (돌 내려놓기)
• 시간 순서대로 정렬해 누적합을 구하면
  → “각 시점의 돌 개수 = 겹치는 구간 수”
  → 그 중 최댓값 = 우리가 구하는 결과