백준 11501, 주식(실버2) [Python]

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

11501번: 주식

---

🐹Description

 

문제

홍준이는 요즘 주식에 빠져있다. 그는 미래를 내다보는 눈이 뛰어나, 날 별로 주가를 예상하고 언제나 그게 맞아떨어진다. 매일 그는 아래 세 가지 중 한 행동을 한다.

1. 주식 하나를 산다.
2. 원하는 만큼 가지고 있는 주식을 판다.
3. 아무것도 안한다.

홍준이는 미래를 예상하는 뛰어난 안목을 가졌지만, 어떻게 해야 자신이 최대 이익을 얻을 수 있는지 모른다. 따라서 당신에게 날 별로 주식의 가격을 알려주었을 때, 최대 이익이 얼마나 되는지 계산을 해달라고 부탁했다.

예를 들어 날 수가 3일이고 날 별로 주가가 10, 7, 6일 때, 주가가 계속 감소하므로 최대 이익은 0이 된다. 그러나 만약 날 별로 주가가 3, 5, 9일 때는 처음 두 날에 주식을 하나씩 사고, 마지막날 다 팔아 버리면 이익이 10이 된다.

입력

입력의 첫 줄에는 테스트케이스 수를 나타내는 자연수 T가 주어진다. 각 테스트케이스 별로 첫 줄에는 날의 수를 나타내는 자연수 N(2 ≤ N ≤ 1,000,000)이 주어지고, 둘째 줄에는 날 별 주가를 나타내는 N개의 자연수들이 공백으로 구분되어 순서대로 주어진다. 날 별 주가는 10,000이하다.

출력

각 테스트케이스 별로 최대 이익을 나타내는 정수 하나를 출력한다. 답은 부호있는 64bit 정수형으로 표현 가능하다.

예제 입력 1 복사

3
3
10 7 6
3
3 5 9
5
1 1 3 1 2

예제 출력 1 복사

0
10
5

---

🧠 Solve

⚀ 풀이 1 [X], 시간초과

그리디 알고리즘 문제이다. 우선 전체 금액 리스트 중에 최대값이 무엇인지 알 수 있고, 그 최대 가격이 나타나기 전까지는 무조건 사놓는게 가장 큰 이익을 도출 하는 방법이다. 생각보다 시간이 5초로 넉넉하길래 max() 함수로 최대값을 도출한 후 최대값이 중간에 있다면 지금까지 사놓은 주식을 전부 팔고, 비싼 가격을 갱신하는 방법을 사용했고, 그때마다 max() 함수를 사용해 전체 순회를 해야해서 price 리스트의 크기를 줄이는 방법을 생각했는데, O(n^2) 방법으로는 채점 중 통과 하지 못했다.

from sys import stdin
from collections import deque
input = stdin.readline

# 1) 산다. 2) 원하는 만큼 판다. 3) 아무것도안함
# 뒤에 앞에보다 비싼 경우가 있기만 하면 일단 사는게 이득
def solve(p):
    dq = deque(p)
    high = max(p)
    tot_buy = 0
    count = 0
    profit = 0
    while dq:
        now = dq.popleft()
        if now < high :
            tot_buy += now
            count += 1
        else :
            profit += high * count - tot_buy
            if dq :
                high = max(dq)
                tot_buy = 0
                count = 0
                
    return profit
             
T = int(input())
result = []
for _ in range(T):
    N = int(input())
    price = list(map(int, input().strip().split()))

    result.append(solve(price))
print(*result, sep='\n')

 

---

⚁ 풀이 2 [O]

시간을 더 줄일 방법을 생각해보았다. 앞에서부터 for문 순회하면서 단순히 두 값 비교를 통해 최대값을 갱신하는 방법은 빠르지만, 앞에서부터 순회하기에 중간에 최대 가격이 있을 경우, 그 이후에 더 큰 값이 있을거라는 보장을 할 수 가 없는 문제점이 있었다. 그때 뒤를 먼저 탐색을 하면 이러한 케이스를 간편히 처리할 수 있음을 깨닳고 O(n)의 방법으로 간단하게 해결했다.

from sys import stdin

input = stdin.readline

# 1) 산다. 2) 원하는 만큼 판다. 3) 아무것도안함

def solve(p):
    cur_high = p[-1]
    profit = 0
    for i in range(len(p)-2,-1,-1):
        if p[i] > cur_high:
            cur_high = p[i]
        else :
            profit += cur_high - p[i]

    return profit
             
T = int(input())
result = []
for _ in range(T):
    N = int(input())
    price = list(map(int, input().split()))

    result.append(solve(price))
print(*result, sep='\n')