[SWEA] View(1206) - Python(리스트 구현)

1차원 배열에 들어있는 빌딩 높이를 입력받아, 조망이 확보된(2칸 내외에 다른 세대가 없는) 세대의 수를 반환하는 문제이다.

시간복잡도 O(n)

 

SW Expert Academy

 

---

테스트 케이스 및 정답

 

[TC1]

입력 :
100
0 0 225 214 82 73 241 233 179 219 135 62 36 13 6 71 179 77 67 139 31 90 9 37 93 203 150 69 19 137 28 174 32 80 64 54 18 0 158 73 173 20 0 102 107 48 50 161 246 145 225 31 0 153 185 157 44 126 153 233 0 201 83 103 191 0 45 0 131 87 97 105 97 209 157 22 0 29 132 74 2 232 44 203 0 51 0 244 212 212 89 53 50 244 207 144 72 143 0 0

정답 : 691

 

---

풀이과정

 

처음에 문제를 봤을 때 2차원 배열에 건물 높이 만큼 칸을 할당해여 비교하는 방식을 생각하였다. 하지만, 해당 방식은 초기화하는 과정이 오래걸려 다른 방법을 찾아야 했다.

그래서 생각한 것이 비교할 주위 건물을 따로 때어내서 현재 건물의 가장 높은 곳부터 비교한다. 그럼 현재 건물의 높이가 주위 건물의 최댓값보다 작거나, 같으면 넘어가면 되고, 현재 건물이 더 높으면 '현재 건물의 높이 - 주위 건물의 최댓값 = 조망이 확보된 세대의 수'가 된다. 그렇게 현재 건물이 끝났으면 다음 건물로 넘어가 계산한다.

 

---

코드

T = 10

for test_case in range(1, T+1):
    N = int(input())
    buildings = list(map(int, input().split()))

    result = 0
    lst = [-1, -2, 1, 2]
    for i in range(2, N - 2):
        side_lst = []
        for j in lst:
            side_lst.append(buildings[i + j])
        if max(side_lst) >= buildings[i]:
            continue
        result += buildings[i] - max(side_lst)
    print(f'#{test_case}: {result}')

 

 

주석 추가

T = 10 # 전체 TC 개수

for test_case in range(1, T+1): # TC마다
    N = int(input()) # 건물의 개수
    buildings = list(map(int, input().split())) # 건물들의 높이
    result = 0 # 정답
    lst = [-1, -2, 1, 2] # 주위(앞, 뒤 2칸) 건물의 인덱스를 구할 때 사용
    for i in range(2, N - 2): # 건물이 있는 곳부터 
        side_lst = [] # 주위 건물의 높이를 저장할 리스트
        for j in lst: # 주위 건물의 인덱스에 접근
            side_lst.append(buildings[i + j]) # 주위 건물을 인덱스로 접근하여 높이를 sied_lst에 저장
        if max(side_lst) >= buildings[i]: # 주위 건물의 높이의 최댓값이 현재 건물보다 크거나, 같으면
            continue # 넘어감
        result += buildings[i] - max(side_lst) # 세대수 계산하여 결과에 더함
    print(f'#{test_case}: {result}')