[백준/파이썬] 1725 : 히스토그램

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

1725번: 히스토그램

문제 요약 : 히스토그램의 높이가 주어졌다. 히스토그램 내부에 가장 넓이가 큰 직사각형의 크기를 구해라.

플래티넘인데 쉬워보이는데..? 했다가 며칠간 아주아주 치열하게 고민한 문제..

 

맞은 코드는 아래 내리면 풀이에 작성해두었습니다!

 

 

시도 1 )

스택문제인 만큼 스택의 특징을 잘 이용해야할 것이라 생각했다.

그치만 일단은 문제를 어떻게 풀어가야할 지 생각하기 위해 무식하게 부딪혔다.

모든 높이값을 받아온 다음, for문을 돌려서 큰 값을 max해주었다.

# 히스토그램 
import sys
input = sys.stdin.readline

N = int(input())
histogram = []
answer = 0
for _ in range(N):
    histogram.append(int(input()))

for i in range(N):
    tmp = 1
    for j in range(i+1,N):
        if histogram[i] <= histogram[j]:
            tmp += 1
        else :
            break
    answer = max(answer, histogram[i]*tmp)

print(answer)

그런데 틀렸습니다가 나왔다

시간초과가 뜰 줄 알았는데 틀렸습니다..?? 이게 정답 풀이가 아닌 것은 알았지만 왜 틀렸는지 한참을 생각했다.

 

결국 예시를 여러개 넣어서 생각해보니, for문을 기준 다음부터 돌리니까 앞에 있는 막대의 넓이까지 더하지 못한다는 것을 알게 되었다.

이걸 생각하는데 이틀이나 걸리다니.. 역시 자기 코드 틀린건 자기가 제일 못찾는다 ㅠㅠ

 

시도 2 )

# 히스토그램 
import sys
input = sys.stdin.readline

N = int(input())
histogram = []
answer = 0
for _ in range(N):
    histogram.append(int(input()))

for i in range(N):
    tmp = 1
    for j in range(i+1,N):
        if histogram[i] <= histogram[j]:
            tmp += 1
        else :
            break
    for k in range(i-1,-1,-1):
        if histogram[i] <= histogram[k]:
            tmp += 1
        else :
            break
    answer = max(answer, histogram[i]*tmp)

print(answer)

시간초과가 떴다! 드디어!!!!

ㅋㅋㅋㅋ 이제 이걸 스택의 특징을 살려서 구현해보는 것을 생각했다.

 

시도 3 )

# 히스토그램 
import sys
input = sys.stdin.readline

N = int(input())
stack = []  # 인덱스, 값
finish = [] # 인덱스들의 차(가로) * 값(세로)

for i in range(N):
    value = int(input())
    while stack and stack[-1][1] > value:
        pre = stack.pop()
        finish.append((i-pre[0])*pre[1])
    stack.append([i,value])

while stack :
    pre = stack.pop()
    finish.append((N-pre[0])*pre[1])

print(max(finish))

이거 또한 틀렸습니다가 떴는데 침착하게 위의 예시와 같은 일이 일어나고 있는게 아닌지 확인했다.

그 전과 같은 이유로 틀렸다. 앞의 값들을 계산해주고 있지 않다.

 

 

풀이 )

stack : [ 시작지점(0번의 경우 0이들어감), 값 ]

finish : 가로길이 * 세로길이 의 최대값

 

풀이의 흐름

1. 입력값 value를 받는다.
2. start에 i 값을 준다.
3. 만일 스택에 값이 있다면, top의 값과 value값을 비교한다.
4. 값이 크거나 같다면, 스택 top에 있는 값은 더이상 사각형을 확장시키지 못한다는 것을 의미한다.
   1. 고로 사각형의 넓이를 구하여 finish에 넣어준다.
   2. 사각형의 가로는 현재 인덱스 값에서 top의 start 값을 빼서 구한다.
   3. 세로값은 top의 값을 그대로 사용한다.
5. stack에 start와 value 값을 넣어준다.
   1. 이때, start값을 넣어주는이유는 4번의 과정때문이다.
   2. 4번의 과정을 통해 start는 현재 value보다 더 큰 값들의 시작점을 저장하고 있다.
6. stack에 값이 남아있을 수 있기 때문에, while stack을 이용하여 남은 값들의 사각형 넓이를 구하여 finish를 갱신한다.

# 히스토그램 
import sys
input = sys.stdin.readline

N = int(input())
stack = []  # 인덱스, 값
finish = 0 # 인덱스들의 차(가로) * 값(세로)

for i in range(N):
    value = int(input())
    start = i
    while stack and stack[-1][1] >= value:
        start, preValue = stack.pop()
        finish = max(finish,(i-start)*preValue)
    stack.append([start,value])

while stack :
    start, preValue = stack.pop()
    finish = max(finish,(N-start)*preValue)

print(finish)

눈물의 흔적

밑에 맞았습니다와 메모리 차이는 stack[-1][1] >= value에 부등호를 넣고 안넣고 차이다. 넣은게 더 메모리 단축함!