[백준] 단계별로 풀어보기(단계:20,분할 정복,JAVA)6549번, 히스토그램에서 가장 큰 직사각형

문제 링크

6549번: 히스토그램에서 가장 큰 직사각형

---

주의사항

• JAVA를 사용하여 프로그램을 사용하였습니다.
• 백준에서 코드를 작성하였을 때 아래 형태에서 Main에서 결과가 출력되어야 합니다.

public class Main{ 	
	public static void main(String[] args){
    }
}

---

문제 설명

---

접근 방법

문제를 처음 접근할 때에는 분할 정복으로 접근하려고 가장 큰 히스토그램값을 기준으로 분할 정복을 사용해보았지만 실패하였습니다.

계속 여러 방법을 시도하다 실패하여 구글링을 해보았는데 분할 정복을 이용하는 방법과 스택을 이용하는 방법이 존재하였습니다.

둘 중 스택을 이용하는 방법이 많이 간결하고 효율적이라고 판단하여 스택을 이용하여 문제를 해결하였습니다.

사용할 스택에는 히스토그램에 막대기 순서를 저장하였습니다.

위 과정이 스택을 이용하여 해결한 알고리즘의 과정입니다.

(히스토그램의 값을 비교하기 위해서 배열을 사용하였습니다.)

1. 스택에 히스토그램 인덱스를 저장합니다.

2. 스택에 peek()의 해당하는 히스토그램 값이 다음 인덱스가 가리키는 히스토그램 값보다 크거나 같으면 이전 범위에서 만들 수 있는 직사각형을 구합니다.

3. 반복을 끝낸 뒤에 스택에 남아있는 인덱스가 표현하는 범위에 해당하는 직사각형을 구합니다.

4. 결과값에는 직사각형의 넓이 중 가장 큰 것을 출력합니다.

• BufferedReader를 사용하여 입력 값을 받았습니다.
• StringTokenizer를 이용하여 히스토그램 값을 띄어쓰기 기준으로 나누었습니다.
• for문을 통해서 히스토그램 값을 저장할 배열을 초기화하였습니다.
• 직사각형 최대 넓이를 구하는 areaCal함수를 만들었습니다.
• 함수를 실행 후 BufferedWriter에 직사각형 최대 넓이를 저장하였습니다.
• BufferedWriter에 저장된 결과값을 출력하였습니다.

• areaCal함수에서 반복문을 통해 스택과 히스토그램 값이 저장된 배열을 이용하여 구성하였습니다.
• for문에 i를 통해서 직사각형에 범위를 조절하여 넓이를 구하였습니다.
• 히스토그램 크기만큼 돌린 후 스택에 남아있을 수 있는 범위에 대한 직사각형의 넓이를 구하기 위해 반복이 끝난 뒤에 한 번더 수행하였습니다.

 

결과 코드

import java.io.*;
import java.util.*;
public class Main{
	static int[] histogram;		//히스토그램 값 저장 배열
    public static void main(String[] args) throws IOException{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        //입력값 처리하는 BufferedReader
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        //결과값 출력하는 BufferedWriter
        //---------입력값 저장 및 배열 초기화---------
        StringTokenizer st;
        while(true) {
        	String text = br.readLine();
        	if(text.equals("0"))
        		break;
        	st = new StringTokenizer(text, " ");
        	int N = Integer.parseInt(st.nextToken());
        	histogram = new int[N];
        	for(int i=0;i<N;i++) 
        		histogram[i] = Integer.parseInt(st.nextToken());
        	bw.write(areaCal(N) + "\n");	//함수 실행 및 결과 BufferedWriter 저장
        }
        bw.flush();		//결과 출력
        bw.close();
        br.close();
    }
    //---------직사각형 최대 넓이 구하는 함수---------
    public static long areaCal(int N) {
    	Stack<Integer> stack = new Stack<Integer>();	//인덱스 저장 스택
    	long result = Integer.MIN_VALUE;		//결과값
    	for(int i=0;i<N;i++) {
        	//스택 peek()값이 다음 히스토그램값보다 크거나 같을 경우
    		while(!stack.isEmpty() && histogram[stack.peek()]>=histogram[i]) {
    			int height = histogram[stack.pop()];
    			long width;
    			if(stack.isEmpty()) {
    				width = i;	//시작부터 지금까지의 범위
    			}else {		//직사각형 범위
    				width = i - 1 - stack.peek();
    			}
    			result = Math.max(result, width * height);
    		}
    		stack.push(i);
    	}
        //스택에 남아있는 범위의 직사각형 계산
    	while(!stack.isEmpty()) {
    		int height = histogram[stack.pop()];
    		long width;
    		if(stack.isEmpty()) {
    			width = N;
    		}else {
    			width = N - 1 - stack.peek();
    		}
    		result = Math.max(result, width * height);
    	}
    	return result;		//결과 반환
    }
}