알고스팟 울타리 잘라내기 (fence) 문제 파이썬으로 풀기

입력값을 받아 가장 큰 넓이의 직사각형의 크기를 출력하면 된다.

보기엔 쉬워 보였지만, 몇번의 실패를 하고 어떤 알고리즘을 써야 할지 찾아보았다.

분할 정복으로 푼 사람이 꽤 많이 보였으나, 나는 그 방법보단 스위핑이 나아 보여서 스위핑으로 푸는 방법을 참고했다.

출처: https://gurumee92.tistory.com/90

판자 높이의 index를 이용해 계산하는 방식이다.

거의 배끼다 시피 해서 코드를 완성했다.

#fence
import sys
 
 
case = int(sys.stdin.readline())
for i in range(case):
    fencenum = int(sys.stdin.readline())  # 판자 수
    fences = list(map(int, sys.stdin.readline().split()))  # 판자 높이
    fences.append(0)  # 스택의 마지막 요소까지 처리해 줘야 하므로 넣음
    fencestack = []  # 스택 역할을 할 리스트
    result = 0
    length = 0  # 너비
    for j in range(fencenum+1):
        while fencestack and fences[fencestack[-1]] >= fences[j]:  # 스택이 비지 않고, 스택에 저장된 위치의 높이가 현재 높이보다 크다면
            position = fencestack[-1]  # 스택의 마지막 요소
            del fencestack[-1]
            if not fencestack:  # 스택이 비었다면
                length = j
            else:  # 안 비었다면
                length = j - fencestack[-1] - 1
            area = length * fences[position]  # 너비*높이
            result = max(result, area)  # 최대값을 구한다
        fencestack.append(j)
    print(result)  # 출력

 

 

느낀점:

1. 분할정복은 코드를 봐도 잘 이해가 안갔는데 이 방식은 쉽게 이해가 가서 썼다. 스위핑이란 방식이 맘에 드는데 나중에 또 써먹을 기회가 왔으면 한다.

2. 알고스팟 문제는 일주일에 하나라도 푸는데 백준은 풀지도 못하는중.. 시간이 없지만 어떻게라도 만들어야겠다.