[알고리즘] 최대 수익 알고리즘

어제에 이어 오늘도 지금까지 계속 알고리즘만 풀었고.. 일단 이 문제를 풂으로써 3문제 중 2문제를 제대로 끝냈다. 마지막 한 문제는, 전에 풀었으나 12개의 테스트 케이스 중 10개나 타임아웃 / 런타임 에러가 떴고.. 그래서 다시풀어봐야한다.. 하지만 시간이 좀 있으니 오늘은 드디어 다른 공부를 할 수 있게 됐다. 하 행복하다..

문제

주식 투자를 즐기는 홍길동은 어떤 회사의 주식을 다음과 같은 패턴으로 매일 주식 거래를 한다: (1) 주식 한 주를 사든지, (2) 이미 샀던 주식 중 일부를 파든지, 혹은 (3) 매매를 하지 않는다.
홍길동은 어떤 기간 동안 주식 매매를 하여 얻은 이익에 대하여, 얻을 수 있는 최대 이익과 얼마나 차이가 있는지를 알고 싶어한다. 그래서, 이 기간 동안 얻을 수 있는 최대 이익을 계산하기로 하였다. 예를 들어, 3일 동안 주식 가격이 (10, 7, 6)이라면 최대 이익은 0이고, (6, 7, 10)이라면, 최대 이익은 7이다. n일 동안 주식 가격이 주어질 때, 얻을 수 있는 최대 이익을 구하는 프로그램을 작성하시오.

입력 형식

첫째 줄에는 n이 주어진다. n은 2 이상 100,000 이하의 정수이다. 둘째 줄에는 주식 가격(양의 정수)이 날짜 순서대로 n개 주어진다.

출력 형식

얻을 수 있는 최대 이익을 첫 번째 줄에 출력한다.

작성 코드(1: 시간 초과)

a = int(input())
b = list(map(int, input().split()))

benefit = 0
b_max = max(b)
if 2 <= a <= 100000:
    for i in range(0, len(b)):
        if b_max == b[-1]:  # 최대값이 맨 뒤에 있을 경우
            benefit += b_max - b[i]  # 기존 benefit 값에 b_max - b[i]한 값을 더해준다.
        else:  # 최대값이 맨 뒤가 아닐 경우
            b_max = max(b[i:])  # i번째 인덱스 이후에서의 max를 새로 구해준다.
            if b_max == b[i]:  # 최대값이 i번째 값인 경우
                continue  # 그냥 넘어간다.
            else:  # 최대값이 i번째 값이 아닌 경우
                benefit += b_max - b[i]  # 기존 benefit 값에 b_max - b[i]한 값을 더해준다.
print(benefit)

우선 이렇게 한 후 goorm 테스트 케이스를 검증해봤는데, 12개 중 10개는 통과했으나 나머지 두 개가 시간초과가 떴다. 그래서 코드를 다시 보니까,

1. 우선 for문으로 인해 O(n)의 시간 복잡도를 가졌다. 나는 O(n)으로 끝인 줄 알았다.
2. 그런데, 11행의 b_max = max(b[i:]) 에서 다시 한 번 i번째 이후로 순회를 하면서 max값을 찾으므로, O(n)의 시간 복잡도를 가지게 되어 결과적으로 O(n^2)의 시간 복잡도를 갖게 되었다.

11, 12번째 테스트 케이스를 통과하지 못한 것도 이때문이었을 것이다. 그래서, 어떻게 하면 한 번만으로 끝낼 수 있을까 하다가, 뒤에서부터 접근해봐야겠다고 생각했다.

작성 코드 (2: 시간 초과 해결)

a = int(input())
b = list(map(int, input().split()))
benefit = 0
b_max = b[-1] # 최댓값을 마지막 원소로 가정했다.

if 2 <= a <= 100000:
    for i in range(a-2, -1, -1): # b[-1]은 이미 b_max로 지정돼있으므로 두 번째 요소부터 아래로 내려가는 for문 시작
        if b[i] > b_max:  # b[i]가 b_max보다 크면
            b_max = b[i]  # b[i]를 b_max로 바꾸고
        else:  # b[i]가 b_max보다 작으면
            benefit += b_max - b[i]  # 기존 benefit에 b_max에서 b[i]를 뺀 값을 추가한다.

print(benefit)

이렇게 할 경우, 다시 순회하는 것 없이 뒤에서부터 쭉 내려가면서 한 번에 모든 것을 해결하므로, 시간 복잡도도 O(n)에 그친다.

이제 마지막 한 문제만 .. 남았다.. 일단 모레까지 제출해야되니까.. 나머지 한 문제도 풀러 가야겠다..