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

의석이는 동서 방향으로 늘어서 있는 산의 N개의 지점에 대한 높이를 측정했다.

서쪽에서 i번째 지점을 i번 지점이라고 하고, 이 지점의 높이는 hi이다.

특이하게도 두 지점이 같은 hi을 가지는 경우는 없었다.

의석이의 친구 상원이가 의석이에게 “우뚝 선 산”이 몇 개인지 찾는 게임을 제안했다.

어떤 두 지점 i,j(1≤i＜j≤N) 사이에 있는 모든 지점을 볼 때, 즉 구간 [i,j]에 대해 이들의 높이의 형태가 “우뚝 선 산”이라는 것을 다음과 같이 정의하기로 했다.


    다음을 만족하는 k(i＜k＜j)가 존재해야 한다.

    i≤l＜k인 모든 l에 대해 hl＜h(l+1)이 성립.

    k≤l＜j인 모든 l에 대해 hl＞h(l+1)이 성립.


이와 같은 정의에서 두 지점 i와 i+1사이는 우뚝 선 산이 될 수 없음에 주의해야 한다.

자존심이 강한 의석이는 “이 정도는 내가 좀 하지.”라며 자신만만하게 대답했지만, 속으로는 식은땀을 흘리고 있다.

의석이는 자존심을 지키기 위해 상원이 몰래 당신에게 도움을 요청했다.

각 지점의 높이가 주어질 때, 우뚝 선 산이 될 수 있는 구간의 개수를 구하는 프로그램을 만들어 정답을 출력하라.

 

이 문제의 경우 결국 1<3>2 와 같이 가운데 가장 큰 수가 있어야하고 그에 따라서 경우의 수가 나오는 것인데

 

잘 생각 해보면 1<2<3>2 의 경우 1<2<3>2 , 2<3>2 와 같이 두가지가 나오고

 

1<2<3>2>1 의 경우 총 4가지의 경우의 수가 나온다.

 

이를 통해 확인할 수 있는 것은 우뚝 솟은 경우가 있을때 양옆에 우뚝 솟도록 할 수 있는 숫자들의 갯수를 세어

 

좌변의 숫자 갯수 * 우변의 수의 갯수를 하게 되면 이 우뚝 솟은 수의 경우의 수가 모두 구해진다.

 

그렇다면

 

1. 우뚝 솟은 지점을 찾자

2. 양변에 각각 몇개의 숫자가 우뚝 솟게 만들수 있는지 찾자

3. 그 숫자를 곱하여 최종 갯수에 더하고 다음 우뚝 솟은 지점을 찾자

 

이다.

 

이 문제의 경우 저 3가지만 생각한다면 쉽기 때문에 전체코드를 바로 공개하겠다.

 

전체 코드는 다음과 같다.

 

import java.util.Scanner;
public class Solution {
	static int cnt;
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		int T = sc.nextInt();
		for(int p=1;p<=T;p++) {
			cnt = 0;
			int N = sc.nextInt();
			int[] arr = new int[N];
			for(int i=0; i<N; i++) {
				arr[i] = sc.nextInt();
			}
			for(int i=1; i<N-1; i++) {
				if(arr[i-1] < arr[i]) {
					i = check(arr, i);
				}
			}
			System.out.printf("#%d %d%n",p,cnt);
		}
	}
	static int check(int[] arr, int i) {
		int count1 = 0;
		int count2 = 0;
        int index = i;
		for(int q=i-1; q>=0; q--) {
			if(arr[q] < arr[q+1]) count1++;
			else {
				if(q+1 == i) return i;
				break;
			}
		}
		for(int w=i+1; w<arr.length; w++) {
			if(arr[w] < arr[w-1]) {
                count2++;
                index = w-1;
            }
			else {
				if(w-1 == i) return i;
                index = w-1;
				break;
			}
		}
		cnt += count1*count2;
        return index;
	}
}

여담이지만 이 문제의 경우 bufferedReader를 쓰게 되면 라인을 읽는 과정에서 문제가 생겨 부득이하게 Scanner를 사용하였다.