[백준] 6549번 : 히스토그램에서 가장 큰 직사각형 - 파이썬(Python) - 우당탕탕 개발자 되기 프로젝트

 

https://www.acmicpc.net/problem/6549

 

1. 문제 설명

반응형

2. 풀이과정

해당 문제는 히스토그램에서 가장 면적이 넓은 직사각형의 넓이를 구하는 문제이다.

문제를 해결하기 위해서는 스택 자료구조를 활용하여 히스토그램의 막대를 하나씩 가져와 2가지 과정을 수행한다.

우선 첫 번째 과정은 히스토그램의 막대를 하나씩 가져오며 이전 막대의 길이보다 작은 막대가 나올 경우 현재까지 막대의 중에서 가장 큰 직사각형의 넓이를 구한다.

두 번째 과정은 이전 막대보다 크거나 같은 길이의 막대가 나올 경우 해당 막대를 스택에 추가한다.

첫 번째 과정에서 가장 큰 직사각형의 넓이를 구할 때는 현재 막대의 길이보다 큰 막대들만 가지고 가장 큰 직사각형의 넓이를 구해야 한다.

 

1. sys.stdin.readline() 함수를 사용하기 위해 sys 모듈을 불러온다. import sys
2. 0을 입력받기 전까지 반복해야 하므로 무한 반복문을 사용한다. while (True)
   1. 리스트 형태로 값을 입력받는다. li = list(map(int, sys.stdin.readline().split()))
   2. 만약 리스트의 합이 0이면 종료를 의미하므로 무한 반복문을 종료한다. if (sum(li) == 0): break
   3. 종료가 아니라면 가장 앞에 입력된 값을 직사각형의 수로 저장한다. n = li[0]
   4. 정답인 가장 큰 직사각형의 넓이를 저장할 변수를 생성하고 초기화한다. MAX = 0
   5. 스택 자료구조를 활용하기 위해 스택 자료구조를 생성해 준다. stack = []
   6. 히스토그램의 막대 위치와 그 높이를 순서대로 불러온다. for i, h in enumerate(li)
      1. 만약 막대 위치가 0이면 해당 값은 히스토그램의 직사각형 수이므로 그냥 넘어간다. if (i == 0): continue
      2. 만약 스택 자료구조에 값이 있고, 가장 마지막 막대의 높이가 현재 막대의 높이보다 크면 if stack and (stack[-1][1] > h)
         1. 스택 자료구조가 빌 때까지 반복한다. while (stack)
            1. 스택 자료구조에서 값을 가져와 막대의 위치와 높이를 분리한다. idx, height = stack.pop()
            2. 구할 직사각형의 너비를 저장할 변수를 생성하고 막대 하나의 너비인 1을 저장한다. width = 1
            3. 만약 스택 자료구조가 비어있지 않다면 너비를 스택에 추가된 막대 중 가장 마지막 막대의 위치에 1을 더한 값으로 저장한다. if (stack): width = stack[-1][0] + 1
            4. 현재 막대의 위치에서 너비를 뺀 값에 높이를 곱한 값으로 넓이를 구한다. result = (i - width) * height
            5. 이전에 저장된 가장 큰 직사각형의 넓이와 방금 구한 넓이 중 큰 값을 최댓값으로 저장한다. MAX = max(result, MAX)
            6. 만약 스택 자료구조가 비었거나 가장 마지막에 있는 막대가 현재 막대보다 작으면 반복을 종료한다. if (not stack) or (stack[-1][1] <= h): break
      3. 만약 스택 자료구조가 비었거나 가장 마지막에 있는 막대가 현재 막대보다 작으면 막대의 위치와 막대의 높이를 튜플로 추가한다. if (not stack) or (stack[-1][1] <= h): stack.append((i, h))
      4. 반복이 종료된 후 스택 자료구조에 남아있는 막대를 확인한다. while (stack)
         1. 스택 자료구조의 남은 막대를 가져와 막대의 위치와 높이를 분리한다. idx, height = stack.pop()
         2. 구할 직사각형의 너비를 저장할 변수를 생성하고 막대 하나의 너비인 1을 저장한다. width = 1
         3. 만약 스택 자료구조가 비어있지 않다면 너비를 스택에 추가된 막대 중 가장 마지막 막대의 위치에 1을 더한 값으로 저장한다. if (stack): width = stack[-1][0] + 1
         4. 전체 막대의 개수에 1을 더한 결과에서 너비를 뺀 값에 높이를 곱한 값으로 넓이를 구한다. result = (n + 1 - width) * height
         5. 이전에 저장된 가장 큰 직사각형의 넓이와 방금 구한 넓이 중 큰 값을 최댓값으로 저장한다. MAX = max(result, MAX)
      5. 최종적으로 구해진 가장 큰 직사각형의 넓이를 출력한다. print(MAX)

3. 소스코드

import sys

while (True):
    li = list(map(int, sys.stdin.readline().split()))
    if (sum(li) == 0):
        break

    n = li[0]

    MAX = 0
    stack = []
    for i, h in enumerate(li):
        if (i == 0):
            continue

        if stack and (stack[-1][1] > h):
            while (stack):
                idx, height = stack.pop()
                width = 1
                if (stack):
                    width = stack[-1][0] + 1

                result = (i - width) * height
                MAX = max(result, MAX)

                if (not stack) or (stack[-1][1] <= h):
                    break
            

        if (not stack) or (stack[-1][1] <= h):
            stack.append((i, h))

    while (stack):
        idx, height = stack.pop()
        width = 1
        if (stack):
            width = stack[-1][0] + 1

        result = (n + 1 - width) * height
        MAX = max(result, MAX)

    print(MAX)