[백준] 1027 고층 건물 - 구현(Implementation) + 기하학(Geometry) JAVA

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

1027번: 고층 건물

코드설명

구현과 기하학(기울기) 문제입니다.

 

문제 로직입니다.

1. 하나의 빌딩에서 좌측과 우측 빌딩을 내려봐야합니다.
2. 좌측을 기준으로 하였을때 빌딩에서 멀어질수록 기울기가 더 작아져야 빌딩이 가리지 않고 보입니다.
3. 우측을 기준으로 하였을떄 빌딩에서 멀어질수록 기울기가 더 커져야 빌딩이 가리지 않고 보입니다.

문제 구현중에서 유의해야할점들은,

 

1. 처음 기울기 처리 ( i == idx - 1 )

//기준좌표에서 왼쪽빌딩 확인 ( 기울기가 더 작아져야합니다. )
for(int i=idx - 1; i >=0; i--) {

    //기울기 : ( 기준의 가로좌표 - 비교의 가로좌표 ) * ( 기준의 세로좌표 - 비교의 세로좌표 ) 
    double inclination = (double) ( arr[idx] - arr[i] ) / ( idx - i );
    //이전 기울기와 비교하여 기울기가 더 작아져야합니다. 
    if( standardInclination > inclination || i == idx - 1) {
        cnt += 1;
        standardInclination = inclination;
    }
}

• 여기서 처음에 i == idx -1 이 아닌, standardInclination == 0 일경우로 생각하여 진행했지만, standardInclination 이 계산도중 0 으로 변경되어 연산이 더 지속될 수 잇으므로 i == idx - 1 로 처리하여 첫번째 경우로 처리하도록 합니다.

2. 기울기가 크거나 같은경우가 아닌 큰 경우나 작은경우만 작동합니다.

if( standardInclination > inclination || i == idx - 1) {

• 처음에 standardInclination >= inclination 으로 처리하였으나, 기울기가 같을경우 해당 빌딩은 가려져서 보이지 않습니다.

3. 처음에는 while문으로 접근하여 진행했는데, 이 문제 같은경우 for문으로 Indexing처리하며 하나씩 내려오도록 처리하는것이 효율적입니다. 추가로, 특정 조건에 맞지 않을경우 for문을 break하도록 처리하였었는데, 이 문제같은경우 if문안의 조건에 일치한다면 성공하도록 하는 로직이 훨씬 더 논리가 간결해집니다.

또한, 왼쪽의 기울기를 살펴본다고 했을때 현재 보이지않는다고해도 다른 멀리 있는 건물이 보일 수 있기에 모든 건물을 다 확인해야합니다.

beforeHeight_Weight = Integer.MIN_VALUE;
//기울기가 더 커져야 합니다.
while(right <= N - 1) {
//    		System.out.println(arr[right]+" ");
    double height_weight = (double) ( arr[start] - arr[right]) / ( start - right );

    //기울기가 더 커져야만 합니다.
    if(beforeHeight_Weight < height_weight || right == start + 1) {
        beforeHeight_Weight = height_weight;
        result += 1;
    }
    right += 1;	
}

 

코드

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

public class Main {
	public static int N, M;
	public static int[] arr;
	public static int answer = 0;
    public static void main(String[] args) throws IOException{
    	BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    	StringTokenizer st = new StringTokenizer(br.readLine()); 	
    	
    	N = Integer.parseInt(st.nextToken());
    	st = new StringTokenizer(br.readLine());
    	arr = new int[N];
    	for(int i=0;i<N;i++) {
    		arr[i] = Integer.parseInt(st.nextToken());
    	}
    	
    	for(int i=0;i<N;i++) {
    		simulate(i);	
    	}
    	System.out.println(answer);
    	
    }
    
    public static void simulate(int idx) {
    	
    	double standardInclination = 0;
    	int cnt = 0;
    	//기준좌표에서 왼쪽빌딩 확인 ( 기울기가 더 작아져야합니다. )
    	for(int i=idx - 1; i >=0; i--) {
    		
    		//기울기 : ( 기준의 가로좌표 - 비교의 가로좌표 ) * ( 기준의 세로좌표 - 비교의 세로좌표 ) 
    		double inclination = (double) ( arr[idx] - arr[i] ) / ( idx - i );
    		//이전 기울기와 비교하여 기울기가 더 작아져야합니다. 
    		if( standardInclination > inclination || i == idx - 1) {
    			cnt += 1;
    			standardInclination = inclination;
    		}
    	}
    	
    	
    	standardInclination = 0;
    	//기준좌표에서 오른쪽빌딩 확인 ( 기울기가 더 커져야 합니다. )
    	for(int i=idx + 1; i < N; i++) {
    		
    		//기울기 : ( 기준의 가로좌표 - 비교의 가로좌표 ) * ( 기준의 세로좌표 - 비교의 세로좌표 )    		
    		double inclination = (double) ( arr[idx] - arr[i] ) / ( idx - i );
    		//이전 기울기와 비교하여 기울기가 더 커져야 합니다. 
    		if( standardInclination < inclination || i == idx + 1) {
    			cnt += 1;
    			standardInclination = inclination;
    		}
    	}
    	answer = Math.max(answer,  cnt);
    }
}