[Baekjoon] 11501번. 주식 - python

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

11501번: 주식

 

정답코드부터 공개

정답코드

k = int(input())
for _ in range(k):
    n = int(input())
    nums = list(map(int, input().split()))
    nums.reverse()
    max = nums[0]
    sum = 0

    for i in range(1,n):
        if max < nums[i]:
            max = nums[i]
            continue
        sum += max - nums[i]
    print(sum)

애초에 반복문을 2번이상 돌리면 안되는 문제였다

nums를 뒤에서부터 읽으면서 max보다 큰 값일 경우는 max값으로 바꿔주고

max보다 작을 경우는 max와의 차이를 sum에 더해주면 됨

 

 

삽질 기록 .. 

메모리 초과 코드

k = int(input())
for _ in range(k):
    n = int(input())
    nums = list(map(int, input().split()))
    tmp = [[] for _ in range(n)]
    answer = 0
    for i in range(n):
        for j in range(i):
            if nums[i] - nums[j] > 0:
                tmp[j].append(nums[i] - nums[j])
    for i in tmp:
        if len(i) != 0:
            answer += max(i)
    print(answer)

수정 후 시간초과 남 (tmp에 append하던 방식 → 그때마다 max값을 구하도록 수정)

k = int(input())
for _ in range(k):
    n = int(input())
    nums = list(map(int, input().split()))
    tmp = [0 for _ in range(n)]
    answer = 0
    for i in range(n):
        for j in range(i):
            if nums[i] - nums[j] > 0:
                tmp[j] = max(tmp[j], nums[i] - nums[j])
    print(sum(tmp))

아예 다른 방법으로 수정

 

시간초과

k = int(input())
for _ in range(k):
    n = int(input())
    nums = list(map(int, input().split()))
    answer = 0
    while len(nums) > 0:
        m = max(nums)
        idx = nums.index(m)
        tmp = nums[:idx]
        nums = nums[idx+1:]
        for i in range(idx):
            answer += m - tmp[i]
    print(answer)

nums에서 max 값을 찾고, tmp 리스트에 nums의 0부터 max까지 넣어둠

nums는 max 이후의 값들을 넣어두고 반복

예)

nums = [1, 2, 100, 90, 1, 2] 일 때,

[1, 2, 100

/, 90

/, 1, 2]

이렇게 나눈 후 max가 아닌 값들은 max에서 뺀 값을 answer에 더해줌

 

시간초과

k = int(input())
for _ in range(k):
    n = int(input())
    nums = list(map(int, input().split()))
    answer = 0
    end = 0
    start = -1
    while end != n-1:
        m = max(nums[start+1:])
        end = nums.index(m)
        for i in range(start, end):
            answer += m - nums[i]
        start = end
    print(answer)

위 코드에서 nums list를 계속 만들지 않고, start와 end 만들어서 비교

 

시간초과

k = int(input())
for _ in range(k):
    n = int(input())
    nums = list(map(int, input().split()))
    answer = 0
    for i in range(n):
        stock = []
        for j in range(i+1,n):
            if nums[i] < nums[j]:
                stock.append(nums[j]-nums[i])
        if len(stock) != 0:
            answer += max(stock)
    print(answer)