Q. 1206. View (D3)

Q. 1206. View(D3)

 

0. 문제

 

D3 난이도의 문제이고, 구현 문제라고 생각된다.

빌딩들의 높이가 주어지고, 오른쪽/왼쪽 두 칸이 비어있으면 그 집은 조망권이 확보된다고 말할 때,

조망권이 확보되는 세대의 수를 구하는 문제이다.

---

1. 풀이

 

1) 모든 땅에 대해 왼쪽 2칸의 높이의 최대값 & 오른쪽 2칸 높이의 최대값을 저장한다.

2) 그리고 두 값을 현재 땅의 높이와 비교해서,

현재 땅이 양 옆 높이의 최대값보다 높은 경우 그 차이를 결과에 저장하는 방식으로 풀었다.

import java.util.Scanner;
import java.util.StringTokenizer;
import java.io.BufferedReader;
import java.io.FileInputStream;
import java.io.IOException;
import java.io.InputStreamReader;
 
class Solution
{
 
//  static Scanner scanner;
    static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    static StringTokenizer st;
    static StringBuffer sb = new StringBuffer();
    static int[] heights;
    static int buildingCnt;
     
    static void input() throws IOException
    {
        buildingCnt = Integer.parseInt(br.readLine()); 
        heights = new int[buildingCnt];
        st = new StringTokenizer(br.readLine());
        for (int i = 0; i < buildingCnt; i++) {
            int height = Integer.parseInt(st.nextToken());
            heights[i] = height;  
        }
    }
     
    static void pro(int tc) {
 
        int[] leftMaxHeightBuildings = new int[buildingCnt];
        int[] rightMaxHeightBuildings = new int[buildingCnt];
         
        for (int i = 2; i < buildingCnt - 2; i++) {
            leftMaxHeightBuildings[i] = Math.max(heights[i - 1], heights[i - 2]);
            rightMaxHeightBuildings[i] = Math.max(heights[i + 1], heights[i + 2]); 
        }
         
        int res = 0;
        for (int i = 2; i < buildingCnt - 2; i++) {
            int compare = Math.max(leftMaxHeightBuildings[i], rightMaxHeightBuildings[i]);
            if (heights[i] > compare) {
                res += heights[i] - compare; 
            }
             
        }
         
        sb.append('#').append(tc).append(' ').append(res).append('\n');
    }
     
     
     
    public static void main(String args[]) throws Exception
    {
         
//      System.setIn(new FileInputStream("res/input.txt"));
//      scanner = new Scanner(System.in);
        int T = 10;
        for(int test_case = 1; test_case <= T; test_case++)
        {
            input();
            pro(test_case);
        }
        System.out.println(sb);
 
    }
}

---

2. 시간복잡도 계산

 

0) N의 최대값은 1000이다.

1) 빌딩의 높이 저장 - O(N)

2) 풀이 1번 - O(N)

3) 풀이 2번 - O(N)

따라서 시간복잡도는 O(3N)이고, 시간제한은 20초이므로

1초에 약 1억번 연산을 한다고 가정하면, 1초 이내에 풀 수 있다.

---

3. 성능 개선 방안

 

1) 입력값을 받으면서 양 옆의 높이의 최대값을 계산할 수 있다.

(코드가 복잡해지고, 입력과 계산 부분이 합쳐지므로 시도하지 않았다.)

2) 높이가 최대 255으로 2^9이고,int 타입의 경우 2^32로

비트마스킹을 사용하면 하나의 int 자료형에 3개의 빌딩 높이를 넣을 수 있다.

(너무 복잡해 질 것 같아서 시도하지 않았다.)

---