[Swift Algorithm] 주식 BOJ #11501

문제 설명

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

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

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

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

 

입력

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

 

출력

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

 

입출력 예제

입력

3
3
10 7 6
3
3 5 9
5
1 1 3 1 2

출력

0
10
5

 

내 문제 풀이

import Foundation

var testCase = Int(readLine()!)!

for _ in 0..<testCase {
    let day = Int(readLine()!)!
    let stocks = readLine()!.split(separator: " ").map({Int(String($0))!})
    
    var answer = 0
    var max = 0
    
    for i in (0..<day).reversed() {
        if max < stocks[i] { max = stocks[i] }
        else { answer += max - stocks[i] }
    }
    
    print(answer)
}

👉 날 별로 현재 주가보다 추후에 주가가 더 상승하는 날이 있는지 확인해주는 것이 포인트!

따라서 나는 마지막날부터 반대로 반복해주면서 현재 주가보다,

지금까지 검사한 날들의 주가 중 더 높은 날이 존재하는지 체크해주었다.

(문제에서 주어진 입력 예시 중, 1 1 3 1 2 순으로 배치된 주가 배열을 대표로 보면

마지막날인 2부터 검사하는데, max가 0으로 초기화된 상태기 때문에 max를 2로 업데이트한다.

그리고 다음으로 넘어가면 주가가 1인데, max보다 작은 값임을 알 수 있다.

이 때 max보다 현재 주가가 작다는 얘기는 '오늘'이후에 주가가 더 오르는 날이 존재한다는 의미이고,

'오늘' 이후의 날들 중 가장 주가가 높은 때의 주가가 바로 max라는 뜻이다.

따라서 이 때 주식을 하나 사고 max일 때 팔면 수익을 볼 수 있다는 뜻이므로

(max - 현재가)를 전체 수익인 answer에 더해준다.)

• 수익을 누적할 answer 변수와 탐색한 주가 중 가장 높은 주가를 저장할 max 변수를 선언했다.
• 입력받은 주가 배열을 뒤에서부터 반복해주었다.
• max보다 현재가가 높을 경우 max를 업데이트했고,
  max보다 현재가가 낮을 경우 max에서 현재가를 뺀 값을 answer에 더했다.

 

💡 피드백

• 앞에서부터 검사해주면 계속 max를 검색해줘야하므로 시간복잡도가 높아지는데,
  뒤에서부터 검사하면 된다는 점만 캐치하면 쉽게 풀 수 있는 문제같다.

 

---

 

문제

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