[python]백준 6549번 : 히스토그램에서 가장 큰 직사각형

시간 제한	메모리 제한	제출	정답	맞은 사람	정답 비율
1 초	256 MB	16367	3904	2522	25.125%

문제

히스토그램은 직사각형 여러 개가 아래쪽으로 정렬되어 있는 도형이다. 각 직사각형은 같은 너비를 가지고 있지만, 높이는 서로 다를 수도 있다. 예를 들어, 왼쪽 그림은 높이가 2, 1, 4, 5, 1, 3, 3이고 너비가 1인 직사각형으로 이루어진 히스토그램이다.

히스토그램에서 가장 넓이가 큰 직사각형을 구하는 프로그램을 작성하시오.

입력

입력은 테스트 케이스 여러 개로 이루어져 있다. 각 테스트 케이스는 한 줄로 이루어져 있고, 직사각형의 수 n이 가장 처음으로 주어진다. (1 ≤ n ≤ 100,000) 그 다음 n개의 정수 h1, ..., hn (0 ≤ hi ≤ 1,000,000,000)가 주어진다. 이 숫자들은 히스토그램에 있는 직사각형의 높이이며, 왼쪽부터 오른쪽까지 순서대로 주어진다. 모든 직사각형의 너비는 1이고, 입력의 마지막 줄에는 0이 하나 주어진다.

출력

각 테스트 케이스에 대해서, 히스토그램에서 가장 넓이가 큰 직사각형의 넓이를 출력한다.

나의 답

첫번째 코드

def calArea(dic):
    max_result = 0
    print(dic)
    for key in dic:
        for obj in dic[key]:
            if obj*key>max_result:
                max_result=obj*key
    return max_result

def calMaxArea(l,h):
    min = h[0]
    tmp_dic = dict()
    tmp_dic[min]=[1]
    index = 1
    arr = list()
    arr.append(min)
    past_renew = list()

    for i in range(0,l-1):
        past_renew = list(set(arr)) #중복 없애기
        arr = []
        if h[i]>=h[i+1]: # 앞이 뒤보다 크거나 같은 경우
            if h[i+1] in past_renew:
                tmp_dic[h[i+1]].append(tmp_dic[h[i+1]].pop()+1)
            elif h[i+1] in tmp_dic.keys():
                tmp_dic[h[i+1]].append(2)
            else:
                tmp_dic[h[i+1]]=[2]

            arr.append(h[i+1])
            if h[i+1] in past_renew:
                past_renew.remove(h[i+1])

            if min>h[i+1]: # min 갱신
                min = h[i+1]
                if min in tmp_dic.keys():
                    tmp_dic[min].append(index)
                else:
                    tmp_dic[min]=[index]

        else: # 뒤가 더 큰 경우
            if h[i+1] in tmp_dic.keys():
                tmp_dic[h[i+1]].append(1)
            else:
                tmp_dic[h[i+1]]=[1]

            if h[i] in past_renew:
                tmp_dic[h[i]].append(tmp_dic[h[i]].pop()+1)
            elif h[i] in tmp_dic.keys():
                tmp_dic[h[i]].append(2)
            else:
                tmp_dic[h[i]]=[2]

            arr.append(h[i])
            arr.append(h[i+1])
            if h[i] in past_renew:
                past_renew.remove(h[i])
            if h[i+1] in past_renew:
                past_renew.remove(h[i+1])

        index+=1
        tmp_dic[min].pop()
        tmp_dic[min].append(index)
        arr.append(min)
        if min in past_renew:
            past_renew.remove(min)

        for obj in past_renew:
            if obj <= h[i+1]:
                if len(tmp_dic[obj])>=2: # 저장된 value가 2개 이상이면
                    tmp_dic[obj].append(tmp_dic[obj].pop()+1)
                else:
                    tmp_dic[obj]=[tmp_dic[obj].pop()+1]
                arr.append(obj)

    return calArea(tmp_dic)



result = list()
while(1):
    tmp = list(map(int,input().split()))
    length = tmp[0]
    if not(length):
        break
    height = tmp[1:]
    result.append(calMaxArea(length,height))

for res in result:
    print(res)

시간 초과

내가 생각해도 너무 복잡하게 짠 코드라 설명조차 못하겠다..

두번째 코드

def calMaxArea():
    global height
    global area
    if len(height)==1: # 기저사례
        if height[0]>area:
            return height[0]
        else:
            return area

    # 가장 작은 수를 받아서
    min_height = min(height) # O(h)
    min_index = height.index(min_height)

    cal_area = min_height*len(height) 
    if cal_area>area: # 더 큰 값이 나오면 갱신
        area = cal_area


    # 가장 작은 높이가 양끝에 위치하면
    if min_index ==0 or min_index == len(height)-1:
        del height[min_index]
        return calMaxArea()
    else:
        tmp_height = height[min_index+1:]
        height = height[:min_index]
        t1 = calMaxArea()
        height = tmp_height
        t2 = calMaxArea()
        if t1>t2:
            return t1
        else:
            return t2

    # 최대 2log(n)번
    # 총 O(hlog(n))

result = list()
while(1):
    tmp = list(map(int,input().split()))
    length = tmp[0]
    if not(length):
        break
    height = tmp[1:]
    area = 0
    result.append(calMaxArea())

for res in result:
    print(res)

메모리 초과

분할 정복을 사용하였다.

O(hlogn)이 나오는데에서 h의 범위가 너무 큰 수이므로 O(h)가 나오는 min을 개선할 필요가 있다. min은 python 기본 연산자로 O(n)의 시간 복잡도를 가지고 있다. 최소를 찾는 알고리즘 중 O(n) 이하의 시간복잡도를 가진 '세그먼트 트리' 알고리즘이 있다.

https://www.acmicpc.net/blog/view/9

다른 답

결국 메모리 초과가 나와서 정답 코드를 찾아보았더니 https://joosjuliet.github.io/6549/ 이 곳에서 단 10줄 정도로 구현한 코드가 있었다 ㅠ.. 대단하다. 라인 스위핑 + 스택 자료구조 를 이용해서 풀었다. 방법은 본인과 비슷한 것 같은데 훨씬 파이썬이라는 언어에 대한 이해도가 깊은 것 같았다. 아래의 그림은 이 블로그의 코드를 읽고 이해한 대로 그려본 것이다.

=> 스택 자료구조를 사용해서 구현하는 것이 편함

또한 이 방법 말고도 백준 블로그에서 추천한 세그먼트 트리 + 분할정복 이나 세그먼트 트리 + 라인스위핑 방법도 가능하다.

import math

def init(node, start, end):
    global tree_list
    global height
    if start == end:
        tree_list[node-1] = start
    else:
        init(node*2,start,(start+end)//2)
        init(node*2+1,(start+end)//2+1,end)
        if height[tree_list[node*2-1]]<height[tree_list[node*2]]:
            tree_list[node-1] = tree_list[node*2-1]
        else:
            tree_list[node-1] = tree_list[node*2]

def query(node,start,end,i,j):
    global tree_list
    global height
    if i>end or j<start: # 주어진 범위가 전체 범위에 완전히 속하지 않는다면
        return -1 
    if i<=start and end<=j: # 주어진 범위가 전체 범위를 완전히 포함한다면
        return tree_list[node-1] # 해당 범위의 최소값 index를 return 함

    # 주어진 범위가 전체 범위에 속해있다면
    # ex_) 0~4 index의 값이 주어졌을 때, 1~3 index에 대한 최소값을 구하고 싶음
    m1 = query(2*node,start,(start+end)//2,i,j) # 전체 범위를 반으로 자른 범위를 넘기고 왼쪽 노드 값을 넘김
    m2 = query(2*node+1,(start+end)//2+1,end,i,j) # 전체 범위를 반으로 자른 범위를 넘기고 오른쪽 노드 값을 넘김
    if m1==-1:
        return m2
    elif m2==-1:
        return m1
    else:
        if height[m1]<=height[m2]:
            return m1
        else:
            return m2


def maxArea(start, end):
    global tree_list
    global height
    min_index = query(1,0,len(height)-1,start,end)
    area = (end-start+1)*height[min_index]
    if min_index-1>=start:
        tmp = maxArea(start,min_index-1)
        if tmp>area:
            area = tmp
    if min_index+1<=end:
        tmp = maxArea(min_index+1,end)
        if tmp>area:
            area = tmp

    return area



result = list()
while(1):
    input_list = list(map(int,input().split()))
    n = input_list[0]
    if n==0:
        break
    height = input_list[1:]
    tree_list = [0]*(pow(2,math.ceil(math.log(len(height),2))+1)-1)
    init(1,0,n-1)
    result.append(maxArea(0,n-1))
    del tree_list

for obj in result:
    print(obj)

구현해보았지만 계속 런타임오류가 난다. 이유는 long 타입으로 구성하지 않아서 인 것 같은데, python은 애초에 범위가 int형을 초과하면 자동으로 long형으로 변환된다고 한다. 또한, long 형의 강제적 형변환이 무슨 이유에서인지 먹히지 않는다. ㅠㅠ