[BOJ]2304. 창고 다각형

2304. 창고 다각형

❌code1

def warehouse(w_list):
    w_list.sort()    # 받은 리스트를 좌표순으로 정렬
    max_height = 0    # 건물 최대 높이

    for w in w_list:
        if w[1] > max_height:
            max_height = w[1]    # 기둥의 최대 높이

    # 최대 높이를 기준으로 면적 설정
    area = max_height

    # 가장 높은 기둥 왼쪽의 면적 구하기
    local_max = w_list[0][1]
    local_m_i = w_list[0][0]
    i = 0
    while True:
        if w_list[i][1] == max_height:  # 높이가 같은 경우
            area += (w_list[i][0] - local_m_i) * local_max
            break
        elif w_list[i][1] > local_max:  # 더 높은 기둥을 만난 경우
            area += (w_list[i][0] - local_m_i) * local_max
            local_max = w_list[i][1]
            local_m_i = w_list[i][0]
        i += 1

    # 가장 높은 기둥 오른쪽의 면적 구하기
    i = 0
    local_max = w_list[-1][1]
    local_m_i = w_list[-1][0]
    while True:
        if w_list[-1-i][1] == max_height:  # 높이가 같은 경우
            area += (local_m_i - w_list[-1-i][0]) * local_max
            break

        elif w_list[-1-i][1] > local_max:  # 더 높은 기둥을 만난 경우
            area += (local_m_i - w_list[-1-i][0]) * local_max
            local_max = w_list[-1-i][1]
            local_m_i = w_list[-1-i][0]
        i += 1

    return area


N = int(input())

my_w_list = []
for i in range(N):
    my_w_list.append(list(map(int, input().split())))

print(warehouse(my_w_list))

시도

가장 높은 기둥을 중심으로 좌, 우를 나눈다. 가장 높은 기둥의 좌측은 왼쪽에서 오른쪽으로 기둥을 확인해가며 면적을 계산하고 우측은 오른쪽에서 왼쪽으로 기둥을 확인해가며 면적을 계산한다.

문제

가장 높은 기둥이 단 한 개 존재한다는 것을 가정하였고 두 개 이상의 최고 높이를 갖는 기둥이 있을시 답이 제대로 나오지 않았다.

⭕code2

def warehouse(col_list):
    # 기둥 높이를 반영한 창고 바닥 리스트를 만든 이후
    # 내림차순으로 정렬된 기둥 높이를 돌면서
    # 현재 기둥 위치와 다음 기둥 위치 사이의 높이를 두 기둥 중 낮은 기둥 높이로 채움

    # 기둥 높이를 기준으로 내림차순 정렬된 리스트 생성
    check_list = sorted(col_list, key=lambda x: x[1], reverse=True)

    col_list.sort()    # 기둥 리스트를 위치순으로 정렬
    c_list = []    # 기둥의 높이만을 담은 리스트 생성, 창고 바닥을 나타냄

    while True:    # 창고 바닥의 높이를 기록, 기둥이 없으면 0, 기둥이 있으면 해당 높이
        if len(col_list) == 0:    # 기존 리스트에서 기둥이 모두 사라지면 break
            break
        elif col_list[0][0] == len(c_list):
            c_list.append(col_list[0][1])    # 기둥이 있으면 그 높이를 넣음
            col_list = col_list[1:]    # 기존의 리스트에서 제거
        else:
            c_list.append(0)    # 기둥이 없으면 0

    for i in range(len(check_list)-1):
        # 현재 기둥 위치와 다음 기둥 위치를 정하는 두 개의 변수
        x1 = min(check_list[i][0], check_list[i+1][0])
        x2 = max(check_list[i][0], check_list[i+1][0])

        # 기둥 사이의 위치들을 돌며 그 높이가 낮은 기둥 높이보다 낮다면 새로 갱신
        for j in range(x1, x2+1):
            if c_list[j] < check_list[i+1][1]:
                c_list[j] = check_list[i+1][1]

    result = sum(c_list)    # 창고 바닥에 적힌 숫자를 모두 더하면 최종 결과

    return result


N = int(input())

my_col_list = []
for i in range(N):
    my_col_list.append(list(map(int, input().split())))

print(warehouse(my_col_list))

시도

창고의 좌측, 우측에서 접근하면 기둥이 오름차순일 때에는 잘 적용될 수 있는 코드를 짤 수 있지만, 내림차순 일 때에는 실패하였다. 따라서 수평이 아닌 수직으로 접근하고자 생각하여 창고 기둥의 높이를 기준으로 정렬한 리스트를 새로 만든 후 이를 이용하여 창고를 직접 채워나갔다.

문제

기둥을 탐색한 이후 다시 모든 기둥에 대하여 검사를 진행해 비효율적이다.

⭕code3

import sys


def warehouse(start, end, direction):
    curr_column = ()  # 현재 최고 높이 기둥 정보
    area = 0  # 창고 면적
    for idx in range(start, end, direction):
        # 최고 높이 기둥을 넘어서면 중지
        if columns[idx][0] * direction > max_l * direction:
            return area

        if not curr_column:  # 저장된 기둥 정보가 없는 경우 초기 정보 저장
            curr_column = columns[idx]

        # 더 높은 기둥을 만난 경우 면적과 현재 최고 높이 기둥 갱신
        elif curr_column[1] <= columns[idx][1]:
            area += (columns[idx][0] - curr_column[0]) * curr_column[1] * direction
            curr_column = columns[idx]
    return area


N = int(sys.stdin.readline())

# 기둥의 왼쪽 면의 위치, 높이를 튜플로 리스트에 저장
columns = [tuple(map(int, sys.stdin.readline().split())) for _ in range(N)]
columns.sort()  # 왼쪽 면의 위치를 기준으로 정렬

# 최고 높이 기둥의 위치를 구해 이를 기준으로 좌측, 우측 창고를 따로 계산
max_l, max_height = max(columns, key=lambda x: x[1])

ans = warehouse(0, N, 1)  # 최고 높이 기둥의 좌축
ans += warehouse(N - 1, -1, -1)  # 최고 높이 기둥의 우측

print(ans + max_height)

시도

code1의 시도를 다시 이용해 최고 높이 기둥을 기준으로 두 가지 경우를 나누었다.

1. 최고 높이 기둥의 좌측은 좌에서 우로 진행하며 기둥을 탐색하고 최고 높이 기둥을 만나면 그다음 기둥이 등장하면(columns[idx][0] > max_l의 경우)에서 for loop를 끝낸다.
2. 최고 높이 기둥의 우측은 우에서 좌로 진행하며 기둥을 탐색하고 최고 높이 기둥을 만나면 그다음 기둥이 등장하면(columns[idx][0] < max_l의 경우)에서 for loop를 끝낸다.

각각의 경우에 대해 현재 기둥보다 같거나 높은 기둥을 만날 시 면적을 갱신하였다.

요약

창고의 기둥에서 최고 높이의 기둥을 기준으로 양옆을 탐색하는 것이 창고를 한 방향으로 탐색하는 것보다 효율적이다.