[SWEA / Java] 1206번: View (D3)

문제 풀이 날짜: 2023.05.18
포스트 작성일: 2023.05.18

 

* 학습 목적으로 작성하는 글입니다. 풀이가 정석적이지 못할 수도 있습니다.

 

문제 출처

Software Expert Academy 1206번: View (D3) (문제 링크)

 

키워드

완전탐색

 

풀이 접근법

• 입력 tc의 개수는 무조건 10개로 고정이다.
• 단순 완전탐색으로 풀이하였다. N ≤ 1000이며, O(N) 시간 안에 해결이 가능하다.
• 조망권을 측정할 빌딩(i)과 그 좌우에 있는 각각 두 개의 빌딩(i - 2, i - 1, i + 1, i +2)과 높낮이를 비교한다.
  • 좌우 네 개의 빌딩보다 i번째 빌딩이 높으면 조망권을 확보할 수 있는 건물이다.
  • 좌우 네 개의 빌딩 중에서 i보다 낮으면서도 높이가 최대인 것을 찾아(secondHeight) 둘의 높이 차를 구한다. (height[i] - secondHeight) 이것이 조망권이 확보된 세대 수이다.
  • 이를 반복문 끝까지 누적시키면 우리가 찾는 답이 된다.

 

코드

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

public class SWEA1206 {

	public static void main(String[] args) throws NumberFormatException, IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		int T = 10;

		StringBuilder sb = new StringBuilder();
		for(int test_case = 1; test_case <= T; test_case++) {
			int N = Integer.parseInt(br.readLine());
			
			int[] height = new int[N];
			
			StringTokenizer st = new StringTokenizer(br.readLine(), " ");
			for(int i = 0; i < N; i++) {
				height[i] = Integer.parseInt(st.nextToken());
			}
			
			int result = 0;
			for(int i = 2; i < N - 2; i++) {
				int secondHeight = -1;
				
                		//좌우 네 개의 빌딩을 탐색
				for(int j = -2; j <= 2; j++) {
					if(j == 0) {
						continue;
					}
					
                    			//하나라도 i번째 빌딩보다 높으면 탐색을 멈춘다.
					if(height[i + j] > height[i]) {
						secondHeight = -1;
						break;
					}
					
					secondHeight = Math.max(height[i + j], secondHeight);
				}
				
                		//i번째 빌딩이 가장 높다면
				if(secondHeight > -1) {
					result += (height[i] - secondHeight);
				}
			}
			
			sb.append("#" + test_case + " ").append(result).append('\n');
		}
        
        System.out.print(sb);
	}

}

---

 

입력의 크기가 작기 때문에 웬만한 완전탐색으로 풀이가 가능하지 않을까 싶다. 입력의 크기가 지금보다 더 커진다면 다른 방법을 고민해보아야 할 듯하다.

 

git 링크

https://github.com/jinju9553/23-CodingTest/blob/main/week8/day5/SWEA1206.java