[SWEA 4796] 의석이의 우뚝 선 산 (JAVA)

현재 index를 기점으로 1칸 왼쪽과 1칸 오른쪽이 모두 현재 index보다 높이가 높은 경우문제 링크: https://swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AWS2h6AKBCoDFAVT

SW Expert Academy

1. 주의할 점

- 우뚝 선 산의 정의에 따라 한개의 봉우리를 기점으로 여러개의 구간이 있을 수 있다.

- Low와 High 배열을 사용하여 꺽이는 부분에 대한 정보를 저장한다

- 시작부분이 High인 경우: Arr[0]>Arr[1] -> 우뚝 선 산에 포함될 수 없으므로 다음 High로 넘어간다

- 끝부분이 High인 경우: Arr[num-1] < Arr[num] -> 우뚝 선 산에 포함될 수 없으므로 Arr[num]을 High에 포함X

 

2. 구현

- Low 배열에 들어가는 기준: 현재 index를 기점으로 1칸 왼쪽과 1칸 오른쪽이 모두 현재 index보다 높이가 높은 경우

- High 배열에 들어가는 기준:  현재 index를 기점으로 1칸 왼쪽과 1칸 오른쪽이 모두 현재 index보다 높이가 낮은 경우

- 계산

Ex) arr[]  = {1,2,3,4,3,2};

위의 기준에 따라 Low와 High 배열에는 다음과 같이 저장된다

Low[] = {0,5};

High[] ={3};

해당 구간에 존재하는 우뚝 선 산: (3 - 0) * (5 - 3) = 6개

import java.util.Scanner;

public class Solution_d4_4796_의석이의우뚝선산 {
	static int num;
	static long arr[];
	static int high[];
	static int low[];
	public static void main(String[] args) throws Exception{
		Scanner sc = new Scanner(System.in);
		int test =sc.nextInt();
		for(int t=1;t<=test;t++) {
			num = sc.nextInt();
			//초기화
			arr = new long[num+1];
			high = new int[num+1];
			low = new int[num+1];
			
			int hidx=0,lidx=0;
			for(int i=1;i<=num;i++) 
				arr[i]=sc.nextLong();
			if(arr[1]<arr[2]) low[lidx++]=1;		//왼쪽 끝 부분
			for(int i=2;i<=num;i++) {
				if(i==num) {
					if(arr[i-1]>arr[i])	//오른쪽 끝부분
						low[lidx++]=i;	
					 continue;
				}
				if(arr[i-1] < arr[i] && arr[i]>arr[i+1]) high[hidx++]=i;	//봉우리
				else if(arr[i-1]> arr[i] && arr[i] < arr[i+1]) low[lidx++]=i;	//낮은 부분
			}		
			int l=0,h=0;
			int result=0;
			while(l<lidx && h<hidx) {
				if(high[h] < low[l]) h++;		//시작이 내려오면서 시작하는경우
				else {
					int tt=high[h]-low[l];
					tt*=(low[l+1]-high[h]);
					l++; h++;
					result+=tt;
				}
			}
			System.out.println("#"+t+" "+result);
		}
	}
}