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

문제링크: https://swexpertacademy.com/main/code/problem/problemDetail.do?problemLevel=3&contestProbId=AV134DPqAA8CFAYh&categoryId=AV134DPqAA8CFAYh&categoryType=CODE&problemTitle=&orderBy=FIRST_REG_DATETIME&selectCodeLang=PYTHON&select-1=3&pageSize=10&pageIndex=1&&&&&&&&&&

SW Expert Academy

 

첫 SWEA풀이라 D3난이도가 어느정도인지 감이 없어 걱정하며 문제를 읽어나갔다. 읽다보니,,, 어? 생각보다 할만한데? 싶었다. (문제는 링크로 걸어두었다).

 

왼쪽 2칸과 오른쪽 2칸은 항상 높이가 0이라는 조건 덕분에 훨씬 수월하게 풀 수 있었다.

내 알고리즘은 다음과 같다.

1. 왼쪽 3번째 건물부터 자신의 왼쪽 2칸, 오른쪽 2칸 중에서 가장 높은 건물의 높이를 찾는다(Pyhon의 max함수 사용)
2. 자신(현재 보고 있는 건물)의 높이가 1번에서 구한 높이보다 작다면, 조망이 없는 것이므로 아무런 작업을 하지 않고, 크다면 현재 보고 있는 검루의 높이에서 주변 중 가장 높은 건물의 높이를 뺀 값을 구한다.
3. 건물의 높이만큼 1, 2번을 반복한다.

 

T = int(input())
# 여러개의 테스트 케이스가 주어지므로, 각각을 처리합니다.
for test_case in range(1, T + 1):
    building_num = int(input())
    heights = [int(x) for x in input().split()]
    # heights = list(map(int, input().split()))
    ans = 0 # 조망권 있는 가구의 수
    for j in range(2, building_num-2):
        biggest_building = max(heights[j-1], heights[j-2], heights[j+1], heights[j+2]) # 주변 2거리에 있는 가장 높은 건물
        if heights[j] - biggest_building > 0: ans  = ans + (heights[j] - biggest_building)
    print('#{0} {1}'.format(test_case, ans))

 

처음에 메모리초과 오류가 발생해 당황했다. 뭐지?? 하면서 List Comprehension으로 바꿔보기도 하고 변수를 없애보기도 하고...(영향은 거의 없겠지만) 그래도 해결이 안되었다. 그래서 "아 내가 생각한 알고리즘보다 더 좋은게 있나보다!" 하면서 고민했다. 그러다 우연히 이 문제 댓글을 보다가 안 사실인데 문제를 자세히 보면 테스트케이스는 10개로 고정이다. 즉, T값을 입력받아서 문제가 된 것이다.... 그럴 수 있지..

 

T = 10
# 여러개의 테스트 케이스가 주어지므로, 각각을 처리합니다.
for test_case in range(1, T + 1):
    building_num = int(input())
    heights = [int(x) for x in input().split()]
    # heights = list(map(int, input().split()))
    ans = 0 # 조망권 있는 가구의 수
    for j in range(2, building_num-2):
        biggest_building = max(heights[j-1], heights[j-2], heights[j+1], heights[j+2]) # 주변 2거리에 있는 가장 높은 건물
        if heights[j] - biggest_building > 0: ans  = ans + (heights[j] - biggest_building)
    print('#{0} {1}'.format(test_case, ans))

 

어쨋든 풀었죠?