[SWEA] 백만 장자 프로젝트(1859) - PYTHON

1차원 배열을 입력받아 원소 순서별로 사거나 팔 수 있다고 가정할 때, 최대 이익을 구하는 문제이다.

시간복잡도: O(N)

SW Expert Academy

 

---

테스트 케이스

[TC1]

입력: 3 5 9

정답: 10

풀이: 첫째, 둘째 날 물건을 구입해서 셋째 날에 팔면 6 + 4 = 10의 이익을 낼 수 있다.

 

[TC2]

입력: 10 7 6

정답: 0

풀이: 날짜가 지날 수록 가격이 줄어드므로 구매를 하지 않는다.

 

[TC3]

입력: 1 1 3 1 2

정답: 5

풀이: 첫째, 둘째날에 물건을 사서 셋째 날에 팔고, 넷째 날에 물건을 사서 다섯째 날에 팔면 (3 - 1) + (3 - 1) + (2 - 1) = 5의 이익이 난다.

---

풀이과정

 

처음에는 단순히 배열의 최댓값을 구한다음, 최댓값과 모든 원소들과 차이의 합을 구하면 된다고 생각했는데, [TC3]처럼 중간에 판매하고 뒤에서 다시 판매하는 경우가 생기므로 단순히 배열의 최댓값에서 판매를 하면 안 된다.

풀이 방법을 고민하다가 배열의 끝 요소부터 앞으로 가면서 현재까지의 최댓값을 저장하며  현재 요소가 최댓값보다 작다면 그 차이를 정답 값에 더하는 방식(물건 구매)으로 계산하면 되겠다는 생각을 했다. 현재 요소가 최댓값보다 크다면, 최댓값을 갱신하고 다음 요소로 넘어간다.

 

---

코드 

N = int(input())
for i in range(N):
    M = int(input())
    answer = 0
    arr = list(map(int, input().split()))
    sellPrice = 0

    for val in arr[::-1]:
        if val >= sellPrice:
            sellPrice = val
        else:
            answer += sellPrice - val
    print("#", i + 1, " ", answer, sep="")

 

주석 추가

N = int(input()) # 전체 TC 갯수
for i in range(N): # TC마다
    M = int(input()) #배열의 길이 (안쓰임)
    answer = 0 #출력할 정답
    arr = list(map(int, input().split())) #배열 입력 받기
    sellPrice = 0 #현재 판매가격(최댓값)

    for val in arr[::-1]: # 배열 거꾸로 순회
        if val >= sellPrice: #현재 값이 최댓값보다 크거나 같다면
            sellPrice = val #최댓값 업데이트
        else:
            answer += sellPrice - val #아니라면 정답값에 가격차이를 더한다. (현재 값에 구매해서 최댓값에 판다)
    print("#", i + 1, " ", answer, sep="") #출력 양식에 맞춰서 출력