[SWEA] 4796. 의석이의 우뚝 선 산 D4 - Simulation

[SWEA] 4796. 의석이의 우뚝 선 산 D4 - Simulation

제출일 : 2019-09-24

문제 풀이 시간 : 1H

난이도 : ★★☆

Problem

link : https://swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AWS2h6AKBCoDFAVT

Input

첫 번째 줄에 테스트 케이스의 수 T(1≤T≤10)가 주어진다.

각 테스트 케이스의 첫 번째 줄에는 자연수 N(3≤N≤50,000)이 주어진다.

다음 줄에는 N개의 자연수 h1,…,hN (1≤hi≤10^9)이 순서대로 공백 하나로 구분되어 주어진다.

모든 1≤i＜j≤N 에 대해 hi≠hj 이다.

Output

각 줄마다 "#T" (T는 테스트 케이스 번호)를 출력한 뒤, 우뚝 선 산이 될 수 있는 구간의 개수를 출력하라.

Example

input

3
3
1 3 2
3
3 2 1
9
1 4 6 5 3 7 9 2 8

output

#1 1
#2 0
#3 6    

Solution & Inpression

1 2 5 3 2 1

위와 같은 경우 우뚝 선 산이 될수 있는 구간은

1 2 5 3

1 2 5 3 2

1 2 5 3 2 1

2 5 3

2 5 3 2

2 5 3 2 1

총 6가지 = 2 X 3 으로 구할수 있다.

Code

언어 : JAVA

메모리 : 102,944 kb

실행시간 : 1,584 ms

import java.util.*;
import java.io.*;

public class Solution {
    static int N;

    public static void main(String args[]) throws Exception {
        Scanner sc = new Scanner(System.in);
        int T = sc.nextInt();

        for (int tc = 1; tc <= T; tc++) {
            N = sc.nextInt();
            int cnt = 0;

            int[] arr = new int[N];
            for (int i = 0; i < N; i++) {
                arr[i] = sc.nextInt();
            }

            for (int i = 0; i < N - 2; i++) {
                int idx = i; 
                int tmp1 = 0;

                while (arr[idx] < arr[++idx]) {
                    tmp1++;
                    if (!range(idx + 1)) {
                        idx++;
                        break;
                    }
                }
                idx--;

                if (i == idx || idx == (N - 1))
                    continue;

                i = idx - 1;

                int tmp2 = 0;
                while (arr[idx] > arr[++idx]) {
                    tmp2++;
                    if (!range(idx + 1)) {
                        idx++;
                        break;
                    }
                }
                idx--;
                cnt += tmp1 * tmp2;
            }
            System.out.println("#" + tc + " " + cnt);
        }
        sc.close(); // Scanner close
    }

    static boolean range(int x) {
        if (0 <= x && x < N)
            return true;
        return false;
    }
}