<13주차> 고층 빌딩 [이유정]

[zlwmxkdla]

🔵 문제
N개의 빌딩이 일렬로 서 있을 때, 각 빌딩에서 좌우 방향으로 다른 빌딩들이 “보이는” 개수를 센 뒤, 그 중 최댓값을 출력하기N개의 빌딩이 일렬로 서 있을 때, 각 빌딩에서 좌우 방향으로 다른 빌딩들이 “보이는” 개수를 센 뒤, 그 중 최댓값을 출력하기

🔵 문제 접근

• 각 빌딩을 기준점으로 선택해서 모든 빌딩 각각에서 볼 수 있는 빌딩의 개수 세기

• 각 빌딩을 기준으로 왼쪽과 오른쪽의 접근 방식이 다르다. -> 왼쪽으로 갈수록 보이는 빌딩이 되기 위해서는 탐색하는 빌딩으로 만들어지는 기울기가 이전의 최소 기울기보다 작아야 한다 오른쪽으로 갈수록 보이는 빌딩이 되기 위해서는 탐색하는 빌딩으로 만들어지는 기울기가 이전의 최대 기울기보다 커야 한다.

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

public class w13_고층건물 {
    public static void main(String[] args) throws IOException {
        BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));
        int n = Integer.parseInt(bf.readLine());
        StringTokenizer st = new StringTokenizer(bf.readLine());
        int[] arr = new int[n + 1];
        for (int i = 1; i <= n; i++) {
            arr[i] = Integer.parseInt(st.nextToken());
        }

        int answer = 0;
        for (int i = 1; i <= n; i++) {
            int count = 0;

            // 왼쪽 탐색: 기울기 계속 감소
            double maxd = Double.POSITIVE_INFINITY;  
            for (int j = i - 1; j >= 1; j--) {
                double d = (arr[j] - arr[i]) / (double)(j - i);
                if (d < maxd) {
                    maxd = d;
                    count++;
                }
            }

            // 오른쪽 탐색: 기울기 계속 증가
            maxd = Double.NEGATIVE_INFINITY;  
            for (int j = i + 1; j <= n; j++) {
                double d = (arr[j] - arr[i]) / (double)(j - i);
                if (d > maxd) {
                    maxd = d;
                    count++;
                }
            }

            answer = Math.max(answer, count);
        }

        System.out.println(answer);
    }
}

🔵 시간 복잡도

1. 기준 빌딩 (i 번째) 를 1번째부터 N번째까지 모두 순회 -> N회
2. 각 기준마다
   • 왼쪽 탐색 : 최대 i 번 반복 -> 최악 O(N)
   • 오른쪽 탐색 : 최대 N-1 번 반복 -> 최악 O(N)
3. 한 빌딩당 O(N) + O(N) = O(N)

-> 전체 : O(N^2) 인데 문제에서 n <= 50 이라 시간 초과는 발생하지 않음