SWEA 1859. 백만 장자 프로젝트

정답 코드

# 테스트 케이스 개수 T 입력
T = int(input())

# T만큼 반복
for tc in range(1, T + 1):
    # 자연수 N의 개수 입력
    N = int(input())
    # N 리스트 입력
    N_list = list(map(int, input().split()))

    # N_list의 마지막 값을 최대값으로 설정
    max_value = N_list[-1]
    # 이익 변수 초기화
    profit = 0

    # N-2번째 인덱스부터 0번째 인덱스까지 1씩 감소하면서 반복 순회
    for i in range(N - 2, -1, -1):
        # 만약 현재 매매가가 최대값보다 크면 최대값을 변경
        if N_list[i] >= max_value:
            max_value = N_list[i]
        # 현재 매매가가 최대값보다 크지 않으면 차익을 profit 변수에 더해준다
        else:
            profit += max_value - N_list[i]

    # 결과 출력
    print(f'#{tc} {profit}')

주어진 매매가를 11312라고 했을 때 초기 max_value를 2로 설정하고 2보다 크거나 같은 값이 나오면 max_value를 그 요소로 변경. 그게 아니라면 max와의 차익을 누적하는 흐름이다. 

이렇듯 가장 뒷 요소를 max로 설정하고 역방향으로 탐색해야 더 큰 값이 나오기 직전의 이익을 온전히 더할 수 있음.

만약 가장 앞을 최댓값으로 설정하고 순방향 탐색한다면 문제를 해결할 수 없음.

 

내 코드

n = int(input())


def calc(d, p):
    sorted_p = sorted(p)
    _max = sorted_p.pop()
    cart = []
    sum_revenue = 0
    for i in range(d):
        if p[i] < _max:
            cart.append(p[i])
        # 현재값==max
        else:
            # cart가 있으면 팜
            if cart:
                for _ in range(len(cart)):
                    sell = cart.pop()
                    sum_revenue += (p[i] - sell)
            if sorted_p:
                _max = sorted_p.pop()
    return sum_revenue


for i in range(1, n + 1):
    days = int(input())
    price = list(map(int, input().split()))
    print(f'#{i} {calc(days, price)}')

 

내가 작성한 코드를 제출했을 땐 예시는 다 맞지만 채점 결과는 10개 중에 2개밖에 맞지 않는다고 한다.

아직까지 로직의 문제점을 찾지는 못했는데 물어볼 기회가 있으면 이 코드도 피드백해보자.

다만 내 코드가 맞다고 하더라도 정답코드가 훨씬 더 효율적인 건 사실이니 비슷한 유형에 적용해보자