문제 개요

N개의 건물 높이가 주어졌을 때 조망권이 확보된 세대의 수를 출력합니다. 조망권이 확보된 세대라는 것은 왼쪽 2개와 오른쪽 2개의 건물의 높이보다 높은 층에 위치해 있는 세대들 입니다.
ex) 4, 4, 7, 4, 4 일때 높이 7인 건물은 3개의 조망권 확보 세대를 가지고 있습니다.

문제 접근

이제와서 생각해보니 문제의 제한 시간이 길어서 왼쪽과 오른쪽에서 가장 큰 값을 이용해서 views를 구하면 될 것 같긴 합니다.

각 건물들은 자신의 왼쪽 2개의 건물을 보고 주변에서 가장 높은 건물의 높이를 구합니다. 각 건물의 높이와 주변 건물의 높이를 빼서 조망권이 확보된 세대의 수를 계산한 후 이들을 모두 더하면 조망권이 확보된 세대의 수를 구할 수 있습니다.

건물들의 높이가 저장된 배열을 heights, 각 건물들의 조망권이 확보된 세대가 저장된 배열을 views라고 합니다.

i-1, i-2 건물의 번호를 j라고 할 때, i 번째 건물의 views는 다음과 같이 구할 수 있습니다.

1. heights[j] < heigths[i] 일때(왼쪽 건물의 높이가 더 낮을 때)
   1. views[j] = heights[j] (j는 조망권 확보가 불가능)
   2. views[i] = max(views[i], heights[j]) (j 중 가장 큰 건물의 높이)
2. heights[j] > heights[i] 일때(왼쪽 건물의 높이가 더 높을 때)
   1. views[j] = max(views[j], heights[i]) (j번째 건물 근처의 가장 큰 건물의 높이까지 확인)
   2. views[i] = heights[i] (i는 조망권 확보가 불가능)

즉, 근처에 자신보다 큰 건물이 있다면 조망권 확보가 불가능하도록 만들고, 그렇지 않다면 근처(i-2 ~ i+2)에서 가장 큰 건물의 높이를 찾습니다.

$result=\sum_{i=0}^{n}H_i-V_i$

그러면 이 둘을 뺀 값을 모두 더한 것이 최종 정답이 됩니다.

import java.util.ArrayList;
import java.util.Arrays;
import java.util.Scanner;

class Solution
{
    static int max(int a, int b){
        return a>b?a:b;
    }

    public static void main(String args[]) throws Exception
    {
        Scanner sc = new Scanner(System.in);
        int[] heights = new int[1000];
        int[] views = new int[1000];
        int T = 10;
        int n;

        for(int test_case = 1; test_case <= T; test_case++)
        {
            n = sc.nextInt();
            for(int i=0;i<n;i++){
                heights[i] = sc.nextInt();
                for(int j=i-1;j>=i-2;j--){
                    if(j<0){
                        break;
                    }
                    if(heights[j] < heights[i]){
                        views[i] = max(views[i], heights[j]);
                        views[j] = heights[j];
                    }
                    else{
                        views[i] = heights[i];
                        views[j] = max(views[j], heights[i]);
                    }
                }
            }
            int sum = 0;
            for(int i=2;i<n-2;i++){
                sum += heights[i] - views[i];
            }
            Arrays.fill(views, 0);
            System.out.println(String.format("#%d %d", test_case, sum));
        }
    }
}