2374 백준 파이썬

원래는 힙을 사용해서 풀려고 했으나... 도대체 무엇이 반례인지 모르겠지만 계속 틀렸다고 나와서 접근 방식을 바꿨다.

 

실패한 코드

import heapq
n=int(input())
l=[]
cnt=0
heap=[]
for _ in range(n):
    x=int(input())
    l.append(x)
now=l[0]
heapq.heappush(heap,now)
for x in range(n):
    if now!=l[x]:
        now=l[x]
        heapq.heappush(heap,now)
while heap:
    target=heapq.heappop(heap)
    for x in range(n):
        if l[x]==target:
            start=x
            break
    end=start
    for x in range(start,n):
        end=x
        if l[x]!=target:
            break
    if start-1>=0:
        if l[start-1]>l[start]:
            if l[end]>l[start]:
                goal=min(l[end],l[start-1])
            else:
                goal=l[start-1]
        else:
            if l[end]>l[start]:
                goal=l[end]
            else:
                continue
    else:
        if l[end]>l[start]:
            goal=l[end]
        else:
            continue
    cnt+=goal-l[start]
    for x in range(start, end):
        l[x]=goal
    if start==end:
        l[start]=goal
print(cnt)

스택을 이용한 코드 (검색함)

스택을 사용해서 중복되는 숫자의 경우를 처리해준다. 

그리고 남은 숫자와 최대값을 빼서 계산해준다. 도대체 어떻게 하면 이런 생각을 떠올릴 수 있나 싶다.

#https://www.acmicpc.net/problem/2374
n=int(input())
stack=[]
cnt=0
m=0
for _ in range(n):
    x=int(input())
    m=max(m,x)
    if stack:
        if stack[-1]<x:
            cnt+=x-stack.pop()
            stack.append(x)
        else:
            stack.pop()
            stack.append(x)
    else:
        stack.append(x)
while stack:
    cnt+=m-stack.pop()
print(cnt)