[그리디] 코딩테스트 문제 TIL (주식) - 백준 11501번

말하는 감자·2024년 12월 30일

TIL algorithm baekjoon greedy python 그리디 백준 알고리즘 코딩테스트 코딩테스트 준비 파이썬

코딩테스트 유형별 풀이

목록 보기

59/67

오늘 문제는 이전 문제인 게임을 만든 동준이와 접근 방법이 유사합니다. 두 문제를 비교하면서 풀어보면 좋을것 같습니다.

1. 오늘의 학습 키워드

그리디 알고리즘

2. 문제: 11501. 주식

단계: 🥈 실버 2단계
주제:
- 그리디 알고리즘
출처: https://www.acmicpc.net/problem/11501

문제

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

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

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

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

입력

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

출력

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

예제 입력 1

예제 출력 1

0
10
5

3. 문제 풀이

Step1. 문제 이해하기

이 문제는 주식 거래에서 최대 이익을 계산하는 문제입니다.

테스트 케이스에서 미래 주가가 주어질 때, 최대 이익을 얻기 위해 어떤 전략을 써야 할지 계산해야 합니다.

매일 아래 세 가지 중 한 행동을 합니다.

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

주어진 예시를 살펴보겠습니다.

날 수가 3일이고 날 별로 주가가 10, 7, 6입니다.
1. 주가가 계속 감소하므로 최대 이익은 0입니다.
날 수가 3일이고 날 별로 주가가 3, 5, 9입니다.
1. 처음 두 날에 주식을 하나씩 사고, 마지막 날 다 팔아버립니다.
2. 첫 날: 3
3. 둘째 날: 5
4. 셋째 날: (9 - 3) + (9 - 5) = 10의 이익

입출력은 다음과 같습니다:

Input:
- 첫 줄에는 테스트 케이스 수가 주어집니다.
- 그 다음 줄에는 각 테스트 케이스 별로 날의 수를 나타내는 자연수가 주어집니다.
  - 2이상 $10^6$ 이하입니다.
- 그 다음 줄에는 날 별 주가를 나타내는 자연수들이 공백으로 구분되어 순서대로 주어집니다.
Output:
- 각 테스트 케이스 별로 최대 이익을 나타내는 정수 하나를 출력합니다. 답은 부호가 있다고 합니다.

Step2. 문제 분석하기

미래의 주가는 알 수 없습니다. 하지만 주어진 문제는 미래의 주가가 주어집니다. 그렇다면 어떻게 해야 최대의 이익을 구할수있을까요?

바로, 미래의 최고 주가와 비교하여 현재 시점에서 주식을 팔지 여부를 결정해야 합니다.

따라서 뒤에서부터 주가를 역순으로 탐색하면서, 현재까지의 최대 주가를 업데이트하며 이익을 계산합니다.

즉, 매 순간 최대 주가인지를 파악하면서 이익을 계산하기 때문에 그리디 알고리즘 유형이라고 할 수 있습니다.

바로 코드를 설계해보도록 하겠습니다.

Step3. 코드 설계

입력을 읽고 테스트 케이스 수 T를 확인합니다.
각 테스트 케이스에 대해:
- 날 수 N과 주가 배열을 입력받습니다.
- 주가 배열을 역순으로 순회하며 최대 주가를 업데이트하고, 이익을 계산합니다.

각 테스트 케이스의 결과를 출력합니다.

Step4. 코드 구현

import sys
def sol(prices):
    profit = 0
    max_profit = 0
    for price in reversed(prices):
        if price > max_profit:
            max_profit = price
        else:
            profit += max_profit - price
    return profit

T = int(sys.stdin.readline().strip())
for _ in range(T):
    N = int(sys.stdin.readline().strip())
    prices = list(map(int, sys.stdin.readline().split()))
    print(sol(prices=prices))

코드 설명:
- sol 함수:
  - 각 테스트 케이스에 대해 주가를 역순으로 순회하며 최대 주가를 갱신합니다.
  - 현재 주가가 최대 주가보다 낮으면 이익을 누적 계산합니다.
  - 계산된 최대 이익을 결과 리스트에 저장합니다.
- 입력 처리:
  - 테스트 케이스 수 T를 입력받고, 각 테스트 케이스의 N과 주가 리스트를 저장합니다.
- 출력:
  - 각 테스트 케이스에 대해 계산된 최대 이익을 출력합니다.
시간 복잡도: O(N), 날의 수는 최대 $10^6$ 이므로 시간 복잡도 상으로 여유가 있습니다.
결과: