[FENCE] 울타리 잘라내기

Java 로 풀어보는 알고리즘입니다. 📖
코딩테스트를 대비하여 JAVA1.8 부터 제공되는 함수형 API 는 사용하지 않았습니다.

문제 : https://www.algospot.com/judge/problem/read/FENCE

algospot.com :: FENCE

 

풀이입니다. 🤔

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;
    }
}

가장 기본적인 풀이로 모든 경우의 수를 탐색하는 n^2 알고리즘을 만들 수 있으나, n 이 최대 20,000 일 수 있기 때문에 시간초과가 발생합니다. 

대신에 풀 수 있는 방법 중 하나는 부분 문제를 만들어, 결과를 병합하는 분할-정복 알고리즘을 사용하는 것입니다.

 

이 알고리즘은 총 4개의 과정을 재귀로 반복합니다. 

- 울타리의 절반을 기준으로 나눈다. 
- 절반을 기준으로 왼쪽에 가장 큰 직사각형의 크기를 구한다. 

- 절반을 기준으로 오른쪽에 가장 큰 직사각형의 크기를 구한다. 
- 중앙을 기준으로 큰 울타리를 기준으로 확장해가며, 가장 큰 직사각형의 크기를 구한다. 
- 위 세 가지 과정 중 가장 큰 직사각형의 크기를 구한다. 

울타리를 절반으로 나누는 연산이 logN 번 진행되며, 그 과정에서 중앙을 기준으로 완전 탐색을 하는 n 번의 연산이 수행됩니다. 
이 알고리즘의 시간복잡도는 n*logN 입니다.

 

 

이 포스트를 읽어주셔서 감사합니다. 🙇🏻‍♂️