2304_창고 다각형 (JAVA)

2304번: 창고 다각형

import java.util.Scanner;
import java.util.Stack;

public class Main {
	public static void main(String[] args){
		Scanner sc = new Scanner(System.in);
		int N = sc.nextInt();

		int[] gidung = new int[1001];
		int start = 1001; int end = 0;

		for(int i=0; i<N; i++){
			int x = sc.nextInt();
			int y = sc.nextInt();

			gidung[x] = y;
			start = Math.min(x,start);
			end = Math.max(x, end);
		}

		//왼->오 탐색
		Stack<Integer> stack = new Stack<>();
		int temp = gidung[start];
		for(int i=start+1; i<=end; i++){
			if(temp > gidung[i])
				stack.push(i);
			else{
				while(!stack.isEmpty()){
					int n = stack.pop();
					gidung[n] = temp;
				}
				temp = gidung[i];
			}
		}
		stack.clear();

		//오->왼 탐색
		temp = gidung[end];
		for(int i=end-1; i>=start; i--){
			if(temp > gidung[i])
				stack.push(i);
			else{
				while(!stack.isEmpty()){
					int n = stack.pop();
					gidung[n] = temp;
				}
				temp = gidung[i];
			}
		}
		stack.clear();

		//정답 추출 
		int ans = 0;
		for(int i=start; i<=end; i++){
			ans += gidung[i];
		}
		System.out.println(ans);
	}
}

 

왼쪽-현재-오른쪽 으로 비교하면서 gidung[]을 업데이트하는 식으로 풀다가 포기하고 다시 풀었다.

 

왼쪽 -> 오른쪽으로 한쪽 방향으로만 비교해야한다고 생각했는데!

왼->오, 오->왼 으로 한쪽 방향으로 각각 수행한 다음에 답을 출력한다는 방법이 있음에 머리를 탁! 쳤다.

 

 

 

[문제 풀이 생각 과정]

 

1. 입력으로 기둥의 시작과 끝을 기억한다. - start, end 변수

   gidung[위치] = 높이 로 저장한다.

 

2. 왼 -> 오른쪽으로 탐색한다.

   1) 처음 기준(temp)를 gidung[start] 로 설정하고

   2) start+1 ~ end까지 돌면서, 기준보다 작다면 스택에 push한다.

   3) 만약 기준보다 같거나 크다면,

      스택에 들어있는 모든걸 pop하고, gidung[pop한 값]=기준 으로 바꾸어준다.

      기준보다 같거나 큰 값으로 기준을 변경한다.

 

3. 스택 초기화

 

4. 오른쪽 -> 왼쪽으로 똑같이 탐색한다.

 

5. start ~ end 까지 gidung[i]값을 출력할 값에 더해주고, 출력!

 

 

 

[예시]

1. gidung[] = {0, 0, 4, 0, 6, 3, 0, 0, 10, 0, 0, 4, 0, 6, 0, 8, 0, ..., 0} 로 저장된다.

   start = 2

   end = 15

 

2. 왼 -> 오른쪽 탐색 후

   gidung[] = {0, 0, 4, 4, 6, 6, 6, 6, 10, 0, 0, 4, 0, 6, 0, 8, 0, ..., 0}

 

3. 오른 -> 왼쪽 탐색 후

   gidung[] = {0, 0, 4, 4, 6, 6, 6, 6, 10, 8, 8, 8, 8, 8, 8, 8, 0, ..., 0}

 

4. start ~ end 까지 모두 더하는 과정

   ans = 4 + 4 + 6 + 6 + 6 + 6 + 10 + 8 + 8 + 8 + 8 + 8 + 8 + 8 = 98