[백준] 1027번: 고층 건물

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

initial

I thought it was similar to the stack question like https://velog.io/@whitehousechef/%EB%B0%B1%EC%A4%80-17298%EB%B2%88-%EC%98%A4%ED%81%B0%EC%88%98
but this is a bit different. We draw a line between roofs of the buildings and if the line intersects another building (i.e. slope is either too high or too low depending on if building is left or right side of our control variable), then we continue on to the next.

solution

import math
from collections import defaultdict, deque
import sys
input = sys.stdin.readline

n = int(input())

lst = list(map(int,input().split()))
def look_left(index):
    count =0
    tmp = int(10e9)
    for i in range(index-1,-1,-1):
        slope = (lst[index]-lst[i])/(index-i)
        if slope<tmp:
            count+=1
            tmp = slope

    return count

def look_right(index):
    count = 0
    tmp = -int(10e9)
    for i in range(index+1,n):
        slope = (lst[index]-lst[i])/(index-i)
        if slope >tmp:
            count+=1
            tmp= slope

    return count

ans= [0 for _ in range(n)]


for i in range(n):
    count1 = look_left(i)
    count2 = look_right(i)
    ans[i]= count1+count2

print(max(ans))

better

I found a better solution at https://magentino.tistory.com/356

how do you even think like this man. You can iterate just once where to determine if building is visible, it must have a slope greater than the exisiting temporary line segment.

N = int(input())
building_list = list(map(int, input().split()))
answer = [0]*N

for i in range(N-1) :
  max_slope = -float('inf')
  for j in range(i+1, N) :
    slope = (building_list[j] - building_list[i]) / (j - i)
    if slope <= max_slope :
      continue
    max_slope = max(max_slope, slope)
    answer[i] += 1
    answer[j] += 1

print(max(answer))

complexity

The provided code appears to be calculating the maximum number of "peaks" that can be observed in an array lst, where a "peak" is defined as an element that is larger than both its left and right neighbors. The code uses two functions, look_left and look_right, to count the number of peaks to the left and right of each element in the array, respectively. Then, it calculates the sum of these counts for each element and finds the maximum sum, which represents the maximum number of peaks that can be observed.

Let's analyze the time complexity of this code:

1. Parsing Input:

   • Parsing the input values and creating the lst array takes O(n) time, where n is the number of elements in the array.

2. Nested Loops:

   • The look_left and look_right functions both use nested loops. They iterate through the elements to the left and right of the current element and calculate slopes.
   • Each of these functions has a loop that potentially goes through all elements in the worst case. Therefore, each function's time complexity is O(n).

3. Loop Over All Elements:

   • The main loop iterates over all elements in the array (from index 0 to n-1) and calls look_left and look_right for each element.
   • Inside the loop, constant-time operations are performed to calculate slopes, update counts, and store values in the ans array.
   • The overall time complexity of the main loop is O(n).

4. Finding Maximum:

   • After the main loop, the code finds the maximum value in the ans array. Finding the maximum takes O(n) time as it goes through the ans array once.

5. Overall Time Complexity:

   • The dominant factor in the time complexity is the main loop, which is O(n).
   • Therefore, the overall time complexity of the code is O(n).

The space complexity is relatively low as the code mainly uses a few variables to store counts and the ans array, which has a size of n. Therefore, the space complexity is O(n).

In summary, the provided code has a time complexity of O(n) and a space complexity of O(n), making it efficient for processing arrays of moderate size.