[SWEA] 1206. [S/W 문제해결 기본] 1일차 - View D3 JAVA (자바) 풀이

문제 1206번 (브루트포스)

 

왼쪽과 오른쪽으로 창문을 열었을 때, 양쪽 모두 거리 2 이상의 공간이 확보될 때 조망권이 확보된다

조망권이 확보된 세대의 수를 반환해라

 

[EX]

 

연두색으로 색칠된 6세대는 2칸 이상의 공백이 존재하므로 조망권 확보

A와 B는 왼쪽 조망은 2칸 이상 확보, 오른쪽 조망은 한 칸만 확보

C의 경우는 오른쪽 조망은 2칸이 확보, 왼쪽 조망이 한 칸 확보
 

[제약 사항]

 

• 가로 길이는 항상 1000이하
• 맨 왼쪽과 맨 오른쪽 두 칸 공백
• 각 빌딩의 높이는 최대 255

 

 

 

[입력]

: 10개의 테스트케이스

: 각 테스트케이스의 첫 번째 줄에는 건물의 개수 N (4 ≤ N ≤ 1000)

  그 다음 줄에는 N개의 건물의 높이 (0 ≤ 각 건물의 높이 ≤ 255)

  (맨 왼쪽, 오른쪽 두 칸에 있는 건물은 항상 높이 0)

 
[출력]

 : "#테스트케이스 조망권확보수" 출력

 

 

 [과정]

 

 탐색하자 → 브루트포스 / dfs → 조건이 있다 → 백트래킹

 

 해당문제가 브루트포스인 이유는 현재 빌딩의 양 옆으로만 높이를 비교하고 넘어가기 때문이다

 백트래킹일 경우 어떤 특수한 조건에 부합하지 않는다면 다시 이전 단계로 되돌아가 검사한다

 마찬가지로 층마다 검사하는게 아니라 그냥 차이나는 층 수만 계산하면 되므로 dfs도 아니다

 

 

※ 과정 ※
 

•  현건물에서 양 옆 건물들의 높이를 비교하기
  • 현재 건물보다 높아지면 다 제외 해야하므로 옆 건물들 중에 제일 높은 건물만 남긴다 
    • 고로 조건이 따로 필요 없고 max 값만 갱신해준다
    • ( ±2 ) 건물과 ( ±1) 건물의 max 값 비교 (순서 상관 x)
  • 현재 건물 (기준) > 제일 높은 건물 (max값) 이면 조망권 확보

 

 

 [코드]

import java.util.*;
import java.io.*;
 
class Solution
{
    public static void main(String args[]) throws Exception
    {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
         
        for(int t = 1; t <= 10; t++)
        {
            int N = Integer.parseInt(br.readLine());
            int arr[] = new int[N];
            int result =0;
             
            StringTokenizer st = new StringTokenizer(br.readLine());
            for(int i=0; i<N; i++){
                arr[i] = Integer.parseInt(st.nextToken());
            }
             
            for(int j=2; j<N-2; j++){
                int max = 0;
                max = Math.max(arr[j-2], arr[j-1]);
                max = Math.max(max, arr[j+1]);
                max = Math.max(max, arr[j+2]);
                 
                if(max<arr[j]){
                    result += arr[j]-max;
                }
            }
            System.out.println("#"+t+" "+result);
        }
    }
}

 

 

 [해설]
     

 :  for(int t = 1; t <= 10; t++)  10번 반복

        {

            int N = Integer.parseInt(br.readLine());  건물 개수

            int arr[] = new int[N];  건물 높이

            int result =0;

 

            StringTokenizer st = new StringTokenizer(br.readLine());

            for(int i=0; i<N; i++){

                arr[i] = Integer.parseInt(st.nextToken());  건물 높이 입력받기

            }

             

            for(int j=2; j<N-2; j++){

                int max = 0;  

                max = Math.max(arr[j-2], arr[j-1]);  양 옆 건물들 중에 제일 큰 건물만 골라내기 1

                max = Math.max(max, arr[j+1]);  양 옆 건물들 중에 제일 큰 건물만 골라내기 2

                max = Math.max(max, arr[j+2]);  양 옆 건물들 중에 제일 큰 건물만 골라내기 3

                 

                if(max<arr[j]){  양 옆 건물 중 제일 큰 건물보다 현재 건물이 더 높아야 조망권 확보

                    result += arr[j]-max;  높이 차이 저장

                }

            }

            System.out.println("#"+t+" "+result);  출력

        }

    }

 

  

 

 

 

 

이제 풀어보러 갈께요 :)

 

 

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

SW Expert Academy

 

 

* 독학으로 익히는 코딩이라 틀린 것이 있을 수 있습니다. 오류가 있다면 댓글을 통해 알려주세요. 감사합니다. *