[python] 백준 11501번: 주식(Greedy)

#  11501 주식

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

11501번: 주식

⭐ 코드

import sys
input = sys.stdin.readline


T = int(input()) # 테스트 케이스
for _ in range(T):
    day = int(input()) # 날
    price = list(map(int, input().split()))
    benefit = 0

    while True:
        
        if len(price) == 0:
            break
        # [10, 7, 6]
        sell = price.pop()

        for i in reversed(range(len(price))): # 1, 0
            
            if price[i] <= sell:
                benefit += (sell - price[i])
                price.pop()
            else:
                break
    print(benefit)

📝 풀이

처음에는 앞에 있는 인덱스에서 뒤에 있는 인덱스를 탐색하면서 풀었었다. 하지만 그렇게되면 시간복잡도가 커져서 그런지 시간초과가 나왔다. 

 

조건을 살펴보면 비싸질 날이 언제인지 알기 때문에 수익을 무조건 내는 구조이다. 그렇다면 비싸진 날을 기준으로 탐색을 진행하면 어떨까 싶었다. 비싼 가격 기준으로 인덱스를 설정하고 현재 가격보다 이전 가격이 낮다면 수익에 더해주는 방식으로 코드를 작성했다.

🔓 정답 코드 뜯어보기

import sys
input = sys.stdin.readline

T = int(input()) # 테스트 케이스
for _ in range(T):
    day = int(input()) # 날
    price = list(map(int, input().split())) # 주식 가격 리스트
    benefit = 0 # 수익 계산

    while True: # 1번
        
        if len(price) == 0: # 2번
            break
        # [10, 7, 6]
        sell = price.pop() # 3번

        for i in reversed(range(len(price))): # 4번 (1, 0)
            
            if price[i] <= sell: # 5번
                benefit += (sell - price[i])
                price.pop()
            else:
                break
    print(benefit)

# 1번

while문을 통해서 주식 가격을 담은 리스트가 빌 때까지 반복문을 돌려준다.

 

# 2번

주식 가격을 담은 price가 비었다면 모든 가격을 비교했다는 뜻임으로 break를 걸어준다.

 

# 3번

마지막 날을 기준으로 인덱스를 탐색할 것이므로 가장 마지막 날에 담긴 가격을 sell에 저장시킨다.

 

# 4번

가격 하나를 빼준 price의 길이를 reversed를 통해 뒤에서부터 탐색을 시작한다. 테스트케이스 1번을 기준으로 price 배열의 길이가 2이므로 1과 0이 i에 할당되게 된다.

 

# 5번

마지막 날에 뽑은 sell 가격과 price[i]를 비교해서 전날 가격이 작으면 benefit에 마지막 날과 비교값을 차감한 숫자를 더해준다. 그리고 난 후 비교가 끝났으므로 pop을 통해 요소를 제거해준다.

 

최종적으로 benefit을 출력해주면 최대 이익이 된다.