[baekjoon] 백준 11501번(파이썬): 주식

문제

11501번: 주식

- 날 별로 주식의 가격을 알려주었을 때, 최대 이익이 얼마나 되는지 구하는 문제이다.

- 예를 들어 날 수가 3일이고 날 별로 주가가 10, 7, 6일 때, 주가가 계속 감소하므로 최대 이익은 0이 된다.

- 그러나 만약 날 별로 주가가 3, 5, 9일 때는 처음 두 날에 주식을 하나씩 사고, 마지막 날 다 팔아 버리면 이익이 10이 된다.

- 테스트 케이스 수를 나타내는 자연수 T가 주어진다.

- 각 테스트 케이스 별로 첫 줄에는 날의 수를 나타내는 자연수 N(2 ≤ N ≤ 1,000,000)이 주어진다.

- 둘째 줄에는 날 별 주가를 나타내는 N개의 자연수들이 공백으로 구분되어 순서대로 주어진다.

- 날 별 주가는 10,000 이하다.

- 각 테스트 케이스 별로 최대 이익을 나타내는 정수 하나를 출력한다.

- 답은 부호 있는 64bit 정수형으로 표현 가능하다.

알고리즘

- 테스트 케이스를 입력받는다.

- 케이스만큼 반복해 날의 수와 주식의 거래가를 각각 입력받는다.

- 반복문을 통해 각 케이스마다 모든 날을 확인하여 주식의 거래가를 비교한다.

- 주식이 없으면 반복문을 멈춘다.

- 제일 마지막 주식의 거래가와 그 전날에 거래가를 비교한다.

- 마지막 주식의 거래가가 더 크면 주식을 팔아 수익 실현한다.

- 그 전날에 거래가가 크면 마지막 주식을 팝 하고 그 전날에 주식으로 다시 비교한다.

코드

import sys

case = int(sys.stdin.readline())

# 케이스만큼 반복한다.
for _ in range(case):
    # 날
    day = int(sys.stdin.readline())
    # 주식의 거래가
    deal = list(map(int, sys.stdin.readline().split()))
    # 총 수익
    stock_return = 0

    # 모든 날을 확인한다.
    while True:

        # 주식이 없으면 반복문을 멈춘다.
        if len(deal) == 0:
            break
        # 마지막 날 주식의 거래가를 팝하여 전날의 모든 주식 거래가를 비교한다.
        sell = deal.pop()

        # 반복문을 통해 주식의 거래가를 마지막 날에 전날에 주식의 판매가부터 첫 날 주식의 가격까지 거꾸로 확인한다.
        for i in reversed(range(len(deal))):
            # 마지막 주식의 판매가가 전날에 판매가보다 크거나 같을 때
            if sell >= deal[i]:

                # 마지막 날에 주식의 거래가에서 그 전날에 주식의 거래가를 빼줘 수익 실현을 한다.
                stock_return += (sell - deal[i])
                # 주식을 팔았으므로 팝한다.
                deal.pop()

            # 마지막 날에 거래가가 그 전날에 거래가보다 작으면 반복을 멈춘다.
            else:
                break

    print(stock_return)

결과

처음 문제를 풀 때는 첫날 주식의 거래가를 기준으로 하여 그다음 날 주식의 거래가보다 작으면 수익실현을 하는 형식으로 현재 주식보다 큰 주식의 수량과 주식의 가격을 계산해서 풀었다. 그런데 위와 같은 방식으로 풀면 시간 초과가 나오는 것을 알게 되었다. 그래서 반대로 한번 생각을 해보기로 하고 위 코드와 같은 결과가 나왔다. 마지막 날을 기준으로 하여 마지막 날 주식의 거래가와 그 전날에 모든 주식을 하나씩 비교하는 것이다. 마지막 날 주식의 거래가보다 그 전날에 주식의 거래가가 작으면 마지막 날 주식의 거래가에서 그 전날에 주식의 거래가를 빼주어 수익실현을 하면 되는 것으로 간단하게 문제가 수행된다. 반대로 마지막 날 주식의 거래가가 그 전날에 주식의 거래가보다 작으면 거래를 안 하는 것으로 가정하고 수익실현 없이 마지막 날 주식의 거래가 기준을 그 전날에 주식의 거래가로 바꿔주어 위 과정을 수행한다. 

github

junjange/CodingTest