[SWEA] VIEW(1206) - PYTHON

일렬로 나열된 빌딩들의 층 수가 주어지면 모든 빌딩의 각 층에서, 좌우 각각 2개의 빌딩에 대해 조망이 확보되는 층의 개수를 구하는 문제이다. 

시간복잡도: O(N)

SW Expert Academy

---

풀이 방법

빌딩 배열에서 좌, 우 끝의 2개 빌딩은 높이가 0이라고 주어졌으므로, 3~M-2번째 빌딩의 층들만 조망 가능 여부를 검사하면 된다.(M:빌딩의 개수)

검사 방법은 우선 좌, 우 각각 2개의 빌딩에서 가장 높은 빌딩의 층 수를 구한 다음, 현재 빌딩의 층수와 비교한다.
현재 빌딩의 층 수가 더 높다면, 현재 빌딩에서 조망 가능한 층은 없으며, 현재 빌딩이 더 높다면, 높은 층들은 조망이 가능하다.
이렇게 범위 내 조망이 가능한 층들을 구해서 더한 다음 그 수를 출력한다.

---

코드

N = 10
 
for i in range(1, N + 1):
    M = int(input())
    answer = 0
    arr = list(map(int, input().split()))
    for j in range(2, M - 2):
        leftMax = max(arr[j - 1], arr[j - 2])
        rightMax = max(arr[j + 1], arr[j + 2])
        answer += max(arr[j] - max(leftMax, rightMax), 0)
    print("#", i, " ", answer, sep="")
 

주석 추가

N = 10 # TC 개수
 
for i in range(1, N + 1): 
    M = int(input()) # 빌딩 개수
    answer = 0 # 정답값
    arr = list(map(int, input().split())) # 빌딩 열 입력
    for j in range(2, M - 2): # 3 ~ M - 2번째 빌딩 범위에서
        leftMax = max(arr[j - 1], arr[j - 2]) # 왼쪽 2개 빌딩 최대값
        rightMax = max(arr[j + 1], arr[j + 2]) # 오른쪽 2개 빌딩 최대값
        answer += max(arr[j] - max(leftMax, rightMax), 0) # 현 빌딩 높이와 최댓값의 차이, 0 중의 최대값
    print("#", i, " ", answer, sep="") #출력