[알고리즘]강변 조망권 구하는 문제

문제를 요약하면 강변에 건물이 늘어서 있는데,

좌/우 로 2칸씩 공간이 있어야 조망권이 확보 되었다고 판단합니다.

입력된 값들을 순서대로 빌딩의 층수라고 할때 조망권이 확보된 층수의 합을 구하는 문제입니다.

Greedy 알고리즘으로 첫번째 두번째를 Case를 계산하며 답을 찾는 수식 찾았습니다.

result = Min( a – Max( a-2 , a-1) , a – Max(a+1, a+2) ) if result > 0

시간 복잡도는 O(n) 인데 개선 가능한 방법을 고민중이나 찾지 못하겠습니다.

구글링했을때 나온 답보다는 이 코드가 나은거 같은데.. 좋은 코드 있으면 공유 부탁드립니다.

import java.util.Scanner;

public class Solution{
    
    private final static int testCase = 10;
    
    public static void main(String[] args){
        Scanner sc = new Scanner(System.in);
        Solution mh = new Solution();
        for(int inx = 0 ; inx < testCase ; inx++){
            String input1 = sc.nextLine();
            String input2 = sc.nextLine();	
            int buildingNo = Integer.parseInt(input1);
            String[] buildings = input2 != null ? input2.split(" ") : null;
            
            int result = 0;
            if(buildings == null) continue;
            
            for(int inj = 2; inj < buildings.length-2 ; inj++){   
                int testBuilding = Integer.parseInt(buildings[inj]);
                int temp = mh.getMinValue( testBuilding - mh.getMaxValue(buildings[inj-2] , buildings[inj-1]), testBuilding- mh.getMaxValue(buildings[inj+1] , buildings[inj+2]));
                if(temp > 0 ) result += temp;
            }
            System.out.println("#"+String.valueOf(inx+1) + " " + String.valueOf(result));  
        }
    }
    
        public int getMaxValue(String a, String b){
            int a1 = Integer.parseInt(a);
            int b1 = Integer.parseInt(b);
            return a1 > b1 ? a1 : b1;
        }

        public int getMinValue(int a, int b){
            return a < b ? a : b;
        }
    
}

import java.util.Scanner;

public class Solution{

private final static int testCase = 10;

public static void main(String[] args){

Scanner sc = new Scanner(System.in);

Solution mh = new Solution();

for(int inx = 0 ; inx < testCase ; inx++){

String input1 = sc.nextLine();

String input2 = sc.nextLine();

int buildingNo = Integer.parseInt(input1);

String[] buildings = input2 != null ? input2.split(" ") : null;

int result = 0;

if(buildings == null) continue;

for(int inj = 2; inj < buildings.length-2 ; inj++){

int testBuilding = Integer.parseInt(buildings[inj]);

int temp = mh.getMinValue( testBuilding - mh.getMaxValue(buildings[inj-2] , buildings[inj-1]), testBuilding- mh.getMaxValue(buildings[inj+1] , buildings[inj+2]));

if(temp > 0 ) result += temp;

}

System.out.println("#"+String.valueOf(inx+1) + " " + String.valueOf(result));

}

public int getMaxValue(String a, String b){

int a1 = Integer.parseInt(a);

int b1 = Integer.parseInt(b);

return a1 > b1 ? a1 : b1;

}

public int getMinValue(int a, int b){

return a < b ? a : b;

}

출처 : https://www.swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AV134DPqAA8CFAYh&categoryId=AV134DPqAA8CFAYh&categoryType=CODE