[SWEA] 1206. [S/W 문제해결 기본] 1일차 - View (구현)

✍️ 문제 요약

https://swexpertacademy.com/main/code/problem/problemDetail.do?problemLevel=3&contestProbId=AV134DPqAA8CFAYh&categoryId=AV134DPqAA8CFAYh&categoryType=CODE

SW Expert Academy

 

왼쪽 조망과 오른쪽 조망 모두 2칸 이상 확보되었을 때 조망권이 확보되었다고 한다.

조망권이 확보된 세대의 수를 구하라.

💪 무식하게 풀기

2차원 리스트(`board`)에 각 세대를 1로 표현한다.

예를 들어 위 사진과 같은 예시라면, 아래처럼 표시된다. (강물이 천장 방향이라고 생각하면 된다.)

 

그리고 각 세대를 순회하며 양 옆 2 칸이 비어있다면(=0 이라면) `cnt += 1`을 한다.

import sys
sys.stdin = open("input.txt", "r")
sys.stdout = open("output.txt", "w")

if __name__ == '__main__':
    TC = 10
    MAX_HEIGHT = 255 # 최대 건물 높이
    for test_case in range(1, TC + 1):
        N = int(input()) # 건물의 수
        board = [[0] * N for _ in range(MAX_HEIGHT)]
        height = list(map(int, input().split()))

        # board init
        for i in range(2,N-2): # 열 (처음과 마지막 0 두 개 뺀 상태에서 순회)
            for j in range(height[i]): # 행
                board[j][i] = 1 # 열은 고정, 행 반복문

        cnt = 0
        for i in range(2,N-2): # 열 (처음과 마지막 0 두 개 뺀 상태에서 순회)
            for j in range(height[i]): # 행
                if board[j][i-1] == 0 and board[j][i-2] == 0 and board[j][i+1] == 0 and board[j][i+2] == 0: # 조망권 보장
                    cnt += 1

        print('#{} {}'.format(test_case, cnt))

 

✨ 우아하게 풀기

건물을 순회하면서, 해당 건물(`height[i]`)의 왼쪽과 오른쪽 각각 2개의 건물 높이를 비교하는 풀이이다.

 

1. (해당 건물을 제외하고) 왼쪽 2개의 건물과 오른쪽 2개의 건물 중 최대 높이(`mx`)를 구한다.

    1-1. 1번에서 구한 최댓값(`mx`)이 해당 건물의 높이(`height[i]`)보다 크면, 그 건물 전체에 조망권이 보장된 세대가 없는 것이다.

    1-2. 1번에서 구한 최댓값(`mx`)보다 해당 건물의 높이(`height[i]`)가 크면, 그 건물의 일부 세대는 조망권이 보장된다.

2. 1-2의 경우, 조망권이 보장된 세대의 수는 `height[i]-mx`이다. 이를 누적하여 최종 답을 구한다.

import sys
sys.stdin = open("input.txt", "r")
sys.stdout = open("output.txt", "w")

if __name__ == '__main__':
    TC = 1
    for test_case in range(1, TC + 1):
        N = int(input())
        height = list(map(int, input().split()))
        
        cnt = 0
        for i in range(2, N - 2): # 처음과 마지막 0 두 개 뺀 상태에서 순회
            mx = max(height[i - 2], height[i - 1], height[i + 1], height[i + 2])
            if height[i] > mx: # 조망된 보장된 세대가 존재
                cnt += (height[i] - mx)

        print("#{} {}".format(test_case, cnt))