[FENCE] 울타리 잘라내기
Java 로 풀어보는 알고리즘입니다. 📖
코딩테스트를 대비하여 JAVA1.8 부터 제공되는 함수형 API 는 사용하지 않았습니다.
문제 : https://www.algospot.com/judge/problem/read/FENCE
algospot.com :: FENCE
울타리 잘라내기 문제 정보 문제 너비가 같은 N개의 나무 판자를 붙여 세운 울타리가 있습니다. 시간이 지남에 따라 판자들이 부러지거나 망가져 높이가 다 달라진 관계로 울타리를 통째로 교체
www.algospot.com
풀이입니다. 🤔
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
|
import java.util.*;
public class Main {
private static final int[] fences = new int[20000];
public static void main(String[] args) {
Scanner scanner = new Scanner(System.in);
int cases = scanner.nextInt();
while (cases-- > 0) {
int n = scanner.nextInt();
for (int i = 0; i < n; ++i) {
fences[i] = scanner.nextInt();
}
System.out.println(solve(fences, 0, n - 1));
}
}
// start 와 end 구간의 fences 로 만들 수 있는 가장 큰 직사각형의 크기를 구한다.
private static int solve(int[] fences, int startIndex, int endIndex) {
int length = getLength(startIndex, endIndex);
if (length == 1) return fences[startIndex]; // 기저사례: 구간[start, end] 가 1일 경우, 해당 fence 를 출력.
int midIndex = (startIndex + endIndex) / 2;
// 좌-우 기준 최대값 연산
int max = Math.max(solve(fences, startIndex, midIndex), solve(fences, midIndex + 1, endIndex));
// 중앙 기준으로 최대값 연산
int centerIndex = (length % 2 != 0)
? midIndex
: (fences[midIndex] >= fences[midIndex + 1]) ? midIndex : midIndex + 1;
int lIndex = centerIndex, rIndex = centerIndex;
int minFence = fences[centerIndex];
max = Math.max(max, minFence);
while (inRange(lIndex - 1, startIndex, endIndex) || inRange(rIndex + 1, startIndex, endIndex)) {
int lFence = inRange(lIndex - 1, startIndex, endIndex) ? fences[lIndex - 1] : Integer.MIN_VALUE;
int rFence = inRange(rIndex + 1, startIndex, endIndex) ? fences[rIndex + 1] : Integer.MIN_VALUE;
if (lFence > rFence) --lIndex;
else ++rIndex;
minFence = Math.min(minFence, Math.max(lFence, rFence));
max = Math.max(max, minFence * getLength(lIndex, rIndex));
}
return max;
}
private static int getLength(int startIndex, int endIndex) {
return endIndex - startIndex + 1;
}
private static boolean inRange(int index, int startIndex, int endIndex) {
return startIndex <= index && index <= endIndex;
}
}
|
cs |
가장 기본적인 풀이로 모든 경우의 수를 탐색하는 n^2 알고리즘을 만들 수 있으나, n 이 최대 20,000 일 수 있기 때문에 시간초과가 발생합니다.
대신에 풀 수 있는 방법 중 하나는 부분 문제를 만들어, 결과를 병합하는 분할-정복 알고리즘을 사용하는 것입니다.
이 알고리즘은 총 4개의 과정을 재귀로 반복합니다.
- 울타리의 절반을 기준으로 나눈다.
- 절반을 기준으로 왼쪽에 가장 큰 직사각형의 크기를 구한다.
- 절반을 기준으로 오른쪽에 가장 큰 직사각형의 크기를 구한다.
- 중앙을 기준으로 큰 울타리를 기준으로 확장해가며, 가장 큰 직사각형의 크기를 구한다.
- 위 세 가지 과정 중 가장 큰 직사각형의 크기를 구한다.
울타리를 절반으로 나누는 연산이 logN 번 진행되며, 그 과정에서 중앙을 기준으로 완전 탐색을 하는 n 번의 연산이 수행됩니다.
이 알고리즘의 시간복잡도는 n*logN 입니다.
이 포스트를 읽어주셔서 감사합니다. 🙇🏻♂️
'개발이야기 > 알고스팟' 카테고리의 다른 글
| [BRUTEFORCE] Brute-Force Attack (2) | 2022.01.17 |
|---|---|
| [QUADTREE] 쿼드 트리 뒤집기 (0) | 2022.01.14 |
| [JOSEPHUS] 조세푸스 문제 (0) | 2022.01.09 |
| [CCR] 문자 인식 (0) | 2022.01.09 |
| [SPETIAL] Spatial Concepts Test (0) | 2022.01.09 |