[Boj/백준] 11501 Python

문제출처: https://www.acmicpc.net/problem/11501

11501번: 주식

 

 

1. 문제 접근 방식

처음에는 배열을 순환하면서 자기보다 뒤에 있는 최댓값에서 현재 값을 뺀것을 더하면 될 것(오른쪽에 자신보다 가장 큰 값)이라고 생각했다.

하지만 시간초과가 발생했다.

최댓값을 0으로 세팅해두고 리스트를 반대로 순환하면서 최댓값보다 크다면 최댓값을 갱신해주고 작다면 최댓값-현재값을 더해줌으로써 해결했다.

 

 

2. 내가 푼 코드

<시간초과>

#시간 초과 코드
import sys

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

for _ in range(case):
    test = int(sys.stdin.readline())
    ans=0
    arr=list(map(int,sys.stdin.readline().split()))
    for i in range(test-1):
        if arr[i] < max(arr[i:]):
            ans+=max(arr[i:])-arr[i]
    print(ans)

<새로 푼 코드>

import sys

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

for _ in range(case):
    test = int(sys.stdin.readline())
    ans=0
    maxVal = 0
    arr=list(map(int,sys.stdin.readline().split()))
    for i in range(test-1,-1,-1):
        if arr[i] > maxVal:
            maxVal = arr[i]
        else:
            ans += maxVal - arr[i]
    print(ans)

 

 

3. 결과 및 느낀점

그리디 문제를 계속 풀면서 감을 잡아야 할것 같다.

시간초과를 해결하기 위한 공부 및 노력이 필요하다...