1027. 고층 건물 (Python)

1027번: 고층 건물

 

풀이

 모든 건물에 대하여 왼쪽과 오른쪽으로 볼 수 있는 건물의 수를 카운트하여 가장 많이 보이는 빌딩의 수를 구하면 된다.

 

 기울기(y의 증가량 / x의 증가량)를 이용하여 구할 수 있는데, 이때 왼쪽의 경우는 기울기가 작아져야 볼 수 있는 건물이고 오른쪽의 경우는 기울기가 커져야 볼 수 있는 건물에 해당한다.

 

 위의 예제에서 높이가 7인 건물로 예를 들어보자. 왼쪽에 가장 먼저 건물 2가 있다. 두 건물의 지붕을 잇는 선분의 기울기는 5 (7-2 / 3-2)에 해당한다. 다음 건물 1과 건물 7의 기울기는 3 (7-1 / 3-1)이다. 이는 이전 기울기인 5보다 작아졌으므로 7번 건물에서 1번 건물을 볼 수 있다.

 

 위와 같은 식으로 왼쪽과 오른쪽에서 볼 수 있는 건물의 수를 구하여 더해주면 된다.

 

코드

# 왼쪽의 경우 기울기가 작아져야 볼 수 있는 건물에 해당
def countLeftBuilding(idx):
    minSlope = float('INF') # 최소 기울기 
    cnt = 0 # 볼 수 있는 건물의 수 

    for i in range(idx-1, -1, -1):
        slope = (buildings[idx] - buildings[i]) / (idx - i) # 기울기를 구하여

        # 이전의 최소 기울기보다 더 작아졌을 경우 최소 기울기를 갱신해주고 카운트를 추가한다.
        if minSlope > slope: 
            minSlope = slope
            cnt += 1

    return cnt


# 오른쪽의 경우 기울기가 커져야 볼 수 있는 건물에 해당
def countRightBuilding(idx):
    maxSlope = -float('INF') # 최대 기울기
    cnt = 0 # 볼 수 있는 건물의 수

    for i in range(idx+1, N):
        slope = (buildings[idx] - buildings[i]) / (idx - i) # 기울기를 구하여

        # 이전의 최대 기울기보다 더 커졌을 경우 최대 기울기를 갱신해주고 카운트를 추가한다.
        if maxSlope < slope:
            maxSlope = slope
            cnt += 1

    return cnt


if __name__ == '__main__':
    N = int(input())  # 빌딩의 수
    buildings = list(map(int, input().split()))

    res = 0

    # 모든 건물에 대하여 왼쪽과 오른쪽을 탐색하여 볼 수 있는 건물의 수를 카운트한다.
    for i in range(N):
        left = countLeftBuilding(i)
        right = countRightBuilding(i)

        res = max(res, left + right)

    print(res)