[백준 25393] 교집합 만들기 [Java]

문제

http://boj.ma/25393

요약

• 구간의 시작과 끝이 동일한 교집합 구간을 만들기 위해, 사용된 구간의 최소 수를 구하자.
• N ≤ 300,000 , Q ≤ 300,000

---

풀이 과정

아이디어

단순히 구간 내의 교집합이 아닌, 구간의 시작과 끝이 일치하면서 교집합인 구간을 찾아한다.

1. 질의 구간 $[ l, r ]$은 주어진 구간 $[ l, r ]$과 일치할 수 있다.
2. 질의 구간 $[ l, r ]$은 주어진 구간 $[ l, R ] (R > r), [ L, r ] (L < l)$의 교집합일 수 있다.
3. 그 외에는 질의 구간을 만족하는 구간은 존재하지 않는다.

(1)은 주어진 구간을 그대로 Set에 저장하고, 질의 구간과 비교하면 된다.

// 구간 저장
String in = br.readLine();
set.add(in);

// 구간 탐색
if (set.contains(query)) {
	return 1;
}

(2)는 주어진 구간 $[ l_i, r_i ]$에 대해, $l_{i} = l$인 구간 중 가장 큰 $r_{i}$과, $r_{i} = r$인 구간 중 가장 작은 $l_{i}$을 각각각 maxIntervalRight, minIntervalLeft에 담아주면 된다.

질의 구간 $[ l, r ]$이 두 구간의 교집합이 될 수 있는지 검사하면 된다.

// 구간 저장
String[] temp = in.split(" ");
int l = Integer.parseInt(temp[0]);
int r = Integer.parseInt(temp[1]);
maxIntervalRight.put(l, Math.max(maxIntervalRight.getOrDefault(l, l), r));
minIntervalLeft.put(r, Math.min(minIntervalLeft.getOrDefault(r, r), l));

// 구간 탐색
String[] in = query.split(" ");
int l = Integer.parseInt(in[0]);
int r = Integer.parseInt(in[1]);
if (maxIntervalRight.containsKey(l) && minIntervalLeft.containsKey(r)) {
	if (maxIntervalRight.get(l) > r && minIntervalLeft.get(r) < l) {
		return 2;
	}
}

최적화

N ≤ 3e5이므로, 최악의 경우 maxIntervalRight, minIntervalLeft를 동적으로 N개의 구간을 생성하게 된다.

HashMap의 DEFAULT_INITIAL_CAPACITY가 16이므로, initialCapacity 를 4e5로 늘리면(DEFAULT_LOAD_FACTOR가 0.75이므로) 리사이징이 발생하지 않아 좀 더 효율적으로 수행할 수 있다.

이번에는 HashMap대신, 원시 타입 배열로 1e6 만큼 미리 선언해주자.

이 때, minIntervalLeftdml는 right를 기준으로 가장 넓은 구간(가장 작은 left)을 기록해야 하므로 1e6 이상의 값으로 초기화를 해야 한다.

set = new HashSet<>((int) 4e5);
final int SIZE = (int) 1e6 + 1;
maxIntervalRight = new int[SIZE];
minIntervalLeft = new int[SIZE];
Arrays.fill(minIntervalLeft, Integer.MAX_VALUE);

성능 분석

• 시간 복잡도: $O(1)$
• 제출결과: Accepted / 1,476 → 980 ms / 266,624 → 197,244 KB

---

회고

Set의 리사이징과 Integer wrapper 비용 등을 고려해 initialCapacity 조절과 원시 타입 배열 사용해 메모리는 약 266MB에서 197MB로, 실행 시간은 1.4초에서 0.9초으로 최적화 할 수 있었다.

특히 리사이징은 이론으로만 알고 있었고, 실제 적용해본 경험은 없었는데 이번 문제를 통해 최적화 결과를 직접적으로 확인할 수 있으니 근거있는 최적화를 결과적으로 확인할 수 있어서 재미있었다. 이번 문제의 최적화는 HashSet의 리사이징(Resizing) 오버헤드와 Integer Wrapper Class의 메모리 비용을 절감하는 데 집중했다. 초기 용량(initialCapacity) 설정 시, $2^{19}$(약 52만)까지 잡는 것은 과도한 메모리 할당 대비 큰 이점이 없을 것이라 판단하여, 데이터 개수와 로드 팩터를 고려한 실질적 적정선인 40만으로 설정했다. 이와 함께 자료구조를 원시 타입(Primitive Type) 배열로 전환한 결과, 메모리는 266MB에서 197MB로, 실행 시간은 1.4초에서 0.9초로 개선되었다. 특히 컬렉션 프레임워크의 리사이징 비용은 이론적으로만 인지하고 있던 부분이었는데, 실제 문제 해결에 적용하여 유의미한 성능 차이를 만들어냈다는 점이 인상적이었다.

기존의 이론이 근거 있는 최적화로 증명되는 과정을 PS에서도 확인하니 최적화의 재미를 느낄 수 있었다.

---

참고

문제

http://boj.ma/25393

소스코드

https://github.com/rogi-rogi/problem-solving/blob/main/baekjoon-online-judge/normal/25393.java