소스코드
import sys
input = sys.stdin.readline
result = [] # 결과 출력용 리스트
inputs = [] # 입력 라인 저장용
while True:
line = input().strip().split()
if line == ['0']:
break
n = int(line[0])
arr = list(map(int, line[1:]))
inputs.append((n, arr)) # 튜플 형태 : (직사각형 수, n개의 높이 배열)
# 중간에 겹치는 영역에 대한 크기를 구하는 함수
def get_crossing_size(arr, left_idx, right_idx, mid_idx):
max_size = arr[mid_idx]
min_height = arr[mid_idx]
l = mid_idx
r = mid_idx
while left_idx < l or right_idx > r:
# 오른쪽 먼저 확장해보기(그냥)
if r < right_idx and (l == left_idx or arr[r+1] >= arr[l-1]):
r += 1
min_height = min(min_height, arr[r])
else:
l -= 1
min_height = min(min_height, arr[l])
max_size = max(max_size, min_height * (r - l + 1))
return max_size
# 메인 함수
def recursive_get_largest_size(arr, left_idx, right_idx):
if left_idx > right_idx:
return 0
# 하나만 남은 경우
if left_idx == right_idx:
return arr[left_idx]
# 마법의 요정 구간
mid_idx = (left_idx + right_idx) // 2
left_side_size = recursive_get_largest_size(arr, left_idx, mid_idx - 1)
right_side_size = recursive_get_largest_size(arr, mid_idx + 1, right_idx)
mid_crossing_size = get_crossing_size(arr, left_idx, right_idx, mid_idx)
return max(left_side_size, right_side_size, mid_crossing_size)
for i in range(len(inputs)):
n, arr = inputs[i]
case_result = recursive_get_largest_size(arr, 0, n-1)
result.append(case_result)
print('\n'.join(map(str, result)))
Python
복사
풀이
•
입력에 대해서는
◦
테스트 케이스가 정확히 몇 개라고 안 나와있고, 끝날 때는 0만 있다고 했으니, while문을 돌면서 0이 등장하는 순간까지 반복하고 해당하면 break를 만나 즉시 종료합니다.
◦
inputs 배열에는 슬라이싱을 이용해서 n과 arr로 분리해 튜플 형태로 저장해둡니다.
•
inputs의 개수만큼 반복을 수행합니다.
◦
각 케이스들은 메인 함수를 시작합니다.
▪
이분탐색(재귀)을 진행합니다.
•
기저 조건은 하나만 남아 left_idx == right_idx인 경우입니다. 해당 인덱스의 높이를 반환합니다.
•
왼쪽 부분에서의 가장 큰 넓이, 오른쪽 부분에서의 가장 큰 넓이, 중앙 부분을 포함하는 경우에서의 가장 큰 넓이를 각각 구합니다.
•
3가지 경우에서의 가장 큰 값을 구합니다.
▪
중앙 부분을 포함하는 경우에서의 가장 큰 넓이는 다음과 같이 구합니다.
•
중앙 부분에서 양쪽으로 뻗어나가며 최대값을 구합니다.
◦
중앙에서 시작하는 이유는, 중앙이 포함된 경우를 우선 고려해야하지 않나 싶어서 선택했습니다.
•
l, r 인덱스를 두고 left_idx, right_idx에 도달할 때까지 계속 반복하며 가장 큰 넓이를 구해나갑니다.
◦
메인 함수를 돌고 반환되는 값을 result 배열에 저장합니다.
•
result 배열을 join해 결과를 출력합니다.
복기
•
다른 부분은 다 괜찮았는데, get_crossing_size 함수에서 while 문의 조건을 거는 것과 if 문에서 오른쪽을 먼저 탐색하는 경우에서의 여러 조건들을 어떻게 설정해야할지 계속 망설였습니다.
◦
if 문의 3가지 조건식과 논리연산자를 어떻게 해야 만족할 수 있는지를 캐치하지 못한 것에 대한 이유를 충분히 생각해보고 보완해야겠습니다.