[swea/java] 1206. view

강변에 빌딩들이 옆으로 빽빽하게 밀집한 지역이 있다.

이곳에서는 빌딩들이 너무 좌우로 밀집하여, 강에 대한 조망은 모든 세대에서 좋지만 왼쪽 또는 오른쪽 창문을 열었을 때 바로 앞에 옆 건물이 보이는 경우가 허다하였다.

그래서 이 지역에서는 왼쪽과 오른쪽으로 창문을 열었을 때, 양쪽 모두 거리 2 이상의 공간이 확보될 때 조망권이 확보된다고 말한다.

빌딩들에 대한 정보가 주어질 때, 조망권이 확보된 세대의 수를 반환하는 프로그램을 작성하시오.
 
아래와 같이 강변에 8채의 빌딩이 있을 때, 연두색으로 색칠된 여섯 세대에서는 좌우로 2칸 이상의 공백이 존재하므로 조망권이 확보된다. 따라서 답은 6이 된다.

 

처음에 설계한 알고리즘은 

 

1. 입력되는 건물의 높이를 배열로 선언한 뒤

2. i번째 건물을 기준으로 오른쪽으로 i-1과 i-2 중 높은 건물 - i번째 건물의 높이와

    왼쪽의 i+1 과 i+2 중 높은 건물 - i번째 건물의 높이 중 최솟값을 view에 더하는 방식을 생각했습니다.

package d3.view;
import java.util.*;
public class Solution {
	public static void main(String[] args) {

		int T = 10; //테스트 케이스 총 개수
        
		Scanner sc = new Scanner(System.in);
		int size; //배열 개수
		int focus; // 기준이 되는 아파트 층수
		
		for(int test_case = 1; test_case <= T; test_case++ ) {
			long view = 0; //총 확보된 조망권
			int right = 0;
			int left = 0;
			
			size = sc.nextInt();
			
			int[] building = new int[size];
			for(int i= 0 ; i < size; i++) {
				building[i] = sc.nextInt(); //배열에 값 집어넣기
			}
			
			for(int i = 2 ; i <= size-3 ; i++) {
				if(building[i-1]>building[i-2]) {
					left= minus(building[i], building[i-1]);
				}else {
					//building[1-2]가 더 큰 경우
					left= minus(building[i], building[i-2]);
				}
				if(building[i+1]> building[i+2]) {
					right = minus(building[i], building[i+1]);
				}else {
					right = minus(building[i], building[i+2]);
				}
				
				if(left > right) {
					view += right;
				}else {
					view +=left;
				}
			
			}
			System.out.println("#" + test_case + " " + view);
		}
		
	}
	private static int minus(int a, int b) {
		int result;
		if( a > b ) {
			result = a -b;
		}else {
			result = 0;
		}
		return result;
	}
}

 

결과는 10개 중 6개의 테스트 케이스를 통과하며 오답으로 처리됐습니다..

이유는 제가 i번째 건물보다 주변의 건물이 더 클 경우 minus()함수의 리턴값을 0으로 줬기 때문이라고 생각하는데요.

이렇게 된다면 만약 오른쪽이 i번째 건물보다 더 커서 0을 리턴 받았다면, 오른쪽의 조망권이 확보되지 않은 채로 왼쪽의 값이 조망권으로 채택되어 view에 더해지기 때문입니다.

 

 

그래서 다른 방법을 생각하던 중 그냥 양 옆의 4 건물의 최댓값과 i번째 건물의 차이를 구하면 되는 거 아닌가? 라는 생각이 들었습니다.

 

package d3.view;
import java.util.*;
public class Solution {
	public static void main(String[] args) {

		int T = 10; //테스트 케이스 총 개수
		Scanner sc = new Scanner(System.in);
		int size; //배열 개수
		int focus; // 기준이 되는 아파트 층수
		
		for(int test_case = 1; test_case <= T; test_case++ ) {
			long view = 0; //총 확보된 조망권
			int right = 0;
			int left = 0;
			
			size = sc.nextInt();
			
			int[] building = new int[size];
			for(int i= 0 ; i < size; i++) {
				building[i] = sc.nextInt(); //배열에 값 집어넣기
			}
			
			for(int i = 2 ; i <= size-3 ; i++) {
				int highest = Math.max(building[i-2], Math.max(building[i-1], Math.max(building[i+1], building[i+2])));
				
				if(building[i] - highest > 0)
					view += building[i] - highest;

			}
			System.out.println("#" + test_case + " " + view);
		}
	}
}

그리하여 완성된 최종 코드 입니다!