SWEA
[SWEA] VIEW(1206) - PYTHON
허비1411
2022. 5. 1. 12:19
일렬로 나열된 빌딩들의 층 수가 주어지면 모든 빌딩의 각 층에서, 좌우 각각 2개의 빌딩에 대해 조망이 확보되는 층의 개수를 구하는 문제이다.
시간복잡도: O(N)
SW Expert Academy
SW 프로그래밍 역량 강화에 도움이 되는 다양한 학습 컨텐츠를 확인하세요!
swexpertacademy.com
풀이 방법
빌딩 배열에서 좌, 우 끝의 2개 빌딩은 높이가 0이라고 주어졌으므로, 3~M-2번째 빌딩의 층들만 조망 가능 여부를 검사하면 된다.(M:빌딩의 개수)
검사 방법은 우선 좌, 우 각각 2개의 빌딩에서 가장 높은 빌딩의 층 수를 구한 다음, 현재 빌딩의 층수와 비교한다.
현재 빌딩의 층 수가 더 높다면, 현재 빌딩에서 조망 가능한 층은 없으며, 현재 빌딩이 더 높다면, 높은 층들은 조망이 가능하다.
이렇게 범위 내 조망이 가능한 층들을 구해서 더한 다음 그 수를 출력한다.
코드
|
1
2
3
4
5
6
7
8
9
10
11
12
|
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="")
|
cs |
주석 추가
|
1
2
3
4
5
6
7
8
9
10
11
|
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="") #출력
|
cs |