[백준 알고리즘] 1027번 자바(Java) 고층 건물

문제

세준시에는 고층 빌딩이 많다. 세준시의 서민 김지민은 가장 많은 고층 빌딩이 보이는 고층 빌딩을 찾으려고 한다. 빌딩은 총 N개가 있는데, 빌딩은 선분으로 나타낸다. i번째 빌딩 (1부터 시작)은 (i,0)부터 (i,높이)의 선분으로 나타낼 수 있다. 고층 빌딩 A에서 다른 고층 빌딩 B가 볼 수 있는 빌딩이 되려면, 두 지붕을 잇는 선분이 A와 B를 제외한 다른 고층 빌딩을 지나거나 접하지 않아야 한다. 가장 많은 고층 빌딩이 보이는 빌딩을 구하고, 거기서 보이는 빌딩의 수를 출력하는 프로그램을 작성하시오.

 

입력

첫째 줄에 빌딩의 수 N이 주어진다. N은 50보다 작거나 같은 자연수이다. 둘째 줄에 1번 빌딩부터 그 높이가 주어진다. 높이는 1,000,000,000보다 작거나 같은 자연수이다.

출력

첫째 줄에 문제의 정답을 출력한다.

 

풀이

시간복잡도

• 시간제한 2초(약 2억)에다가 빌딩의 수는 최대 50이라서 초과할일이 없다고 생각했다.
• 각 빌딩 50개를 기준으로 다른 빌딩을 비교해본다고 생각했을때 O(n^2)이다. 

과정

• 기준 빌딩을 기준으로 좌우 빌딩의 기울기를 비교하면서 구하면 된다고 생각했다
• 빌딩이보이는 기준은 빌딩과 빌딩사이의 기울기보다 작은 기울기들만 존재하면 보인다
• 이를 통해 기준 빌딩에서 보이는 가장 큰 기울기를 매번 체크해주는 변수를 만들어 놓고 더 큰 기울기의 빌딩이
  등장하면 값을 치환해주고 cnt++해준다

 

예시

15
1 5 3 2 6 3 2 6 4 2 5 7 3 1 5

아래 그림은 i =7일때(i는 0부터 시작)각 빌딩에 대한 기울기와 그리고 보이는 빌딩을 주황색, 보이지않는 빌딩을

빨간색으로 기울기를 표시했다. 기준은 이제 빌딩과 빌딩사이에 있는 제일 큰 기울기와 비교했을때 그 기울기를 초과하면 cnt++해준다.

 

결국 i=7일때(빌딩 높이 6) 볼 수 있는 빌딩의 수는 6개이다.(좌 3개, 우 3개)

 

 

 

예제 입력 예시

15
1 5 3 2 6 3 2 6 4 2 5 7 3 1 5

 

예제 출력 예시

7

 

소스코드

//1027번 고층건물
//기울기를 구한다음에 기울기가 전꺼보다 낮아야 통과(그러면 이걸로 기울기 대체)

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

public class P1027 {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int N = Integer.parseInt(br.readLine());
        StringTokenizer st = new StringTokenizer(br.readLine());

        int[] buildingHeight = new int[N];
        for (int i = 0; i < N; i++) {
            buildingHeight[i] = Integer.parseInt(st.nextToken());
        }

        int maxCnt = 0;
        for (int i = 0; i < N; i++) {
            double leftHighInclination = -1000000000; //왼쪽 기울기 최대
            double rightHighInclination = -1000000000; //오른쪽 기울기 최대
            int leftCnt = 0; //왼쪽에 볼수 있는 빌딩 수
            int rightCnt =  0; //오른쪽에 볼수 있는 빌딩 수

            for (int j = i-1; j >=0; j--) {
                //기울기 (높이차이)/(i-j)
                double tempInclination = (double)(buildingHeight[j]-buildingHeight[i])/(i-j);
                if(tempInclination>leftHighInclination){
                    leftHighInclination = tempInclination;
                    leftCnt++;
                }
            }

            for (int j = i+1; j < N; j++) {
                //기울기 (높이차이)/(j-i)
                double tempInclination = (double)(buildingHeight[j]-buildingHeight[i])/(j-i);
                if(tempInclination>rightHighInclination){
                    rightHighInclination = tempInclination;
                    rightCnt++;
                }
            }
            if((rightCnt+leftCnt)>maxCnt) maxCnt = rightCnt+leftCnt;
        }
        System.out.println(maxCnt);
    }
}

 

 

 

 

문제 출처

https://www.acmicpc.net/problem/1027

1027번: 고층 건물