[백준 11501번] 주식 (Python) / S2

문제

11501. 주식

코드 1) 87%에서 시간 초과

# 11501번
t = int(input())
for _ in range(t):
    n = int(input())
    numbers = list(map(int,input().split()))

    res = 0
    cnt = 0

    max_number = max(numbers)

    for i in range(n-1):
        if numbers[i] == max_number:                # max 값일 때 모두 팔기!
            if cnt:
                res += (cnt * numbers[i])
                cnt = 0
                max_number = max(numbers[i+1:])     # 다음 max값으로 갱신
            else:
                max_number = max(numbers[i + 1:])
        else:
            res -= numbers[i]                       # max값이 아니면 사기
            cnt += 1

    if cnt:
        res += (cnt * numbers[-1])

    print(res)

접근 방법

max_number에 주가가 제일 큰 날을 지정하고, 그 날이 되기 전까지 주식을 모두 산다.
하루에 한개씩만 살 수 있으므로, cnt에 지금까지 산 주식 개수를 저장하고,
주가가 제일 큰 날이 되면 지금까지 산 주식 개수 * 현재 주가를 곱해서 더해준다.
그리고 그 날 이후의 주가가 제일 큰 날로 max_number을 업데이트 해준다.

만약 주가가 제일 큰 날이 아니면, 주식을 사야하므로
해당 날의 주가만큼 res를 빼주고, cnt에 1을 더해준다.

만약 주가가 제일 큰 날에 산게 아무것도 없으면 (cnt = 0)
max_number만 업데이트해준다.

코드2) 정답

# 11501번
t = int(input())
for _ in range(t):
    n = int(input())
    numbers = list(map(int,input().split()))

    res = 0

    max_number = numbers[-1]

    for i in range(n-2,-1,-1):
        if numbers[i] > max_number:
            max_number = numbers[i]         # 최대값보다 크면 max_number 업데이트

        else:
            res += (max_number - numbers[i])        # 아니면 이득생김 -> 최대값에서 지금 사는 값 뺀만큼!
    print(res)

접근 방법

첫번째 코드에서 max_number을 업데이트 해주는 부분에서 시간초과가 일어나는 것 같아서 방법을 바꿔주었다.
뒤에서부터 큰 값일때 팔고, 작은값이면 사야 하므로
max_number보다 큰 값이면 max_number을 업데이트 해주고
작은값이면 max_number에서 해당 주가를 뺀 값이 이득이므로 max_number - numbers[i]만큼을 더해준다!