[Swift 알고리즘] 백준 11501 주식

안녕하세요 코코종입니다.

2일차에 푼 문제 '주식'입니다. 처음에는 알고리즘을 잘못짜서 실패했었는데 그 내용도 보여드릴게요

//
//  main.swift
//  BackJoon
//
//  Created by kokojong on 2023/04/03.
//

import Foundation
// 11501 주식 그리디 실2

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

// idea: 올라가거나 같을 때만 산다. 내려갈때는 암것도 안한다.


let t = Int(readLine()!)!

for _ in 0..<t {
    let n = Int(readLine()!)!
    let arr = readLine()!.components(separatedBy: " ").map { Int($0)! }
    
    var gain = 0 // 이득
    var cost = 0 // 지불한 가격
    var cnt = 0 // 주식 보유 수
    
    var flow: [Bool] = []
    
    for i in 0..<n - 1 {
        flow.append(arr[i] <= arr[i+1])
    }
//    print(flow)
    
    for i in 0..<n-1 {
        if flow[i] { // 앞으로 오르면 -> 주식 구매
            cnt += 1
            cost += arr[i]
        } else { // 앞으로 떨어지면 -> 주식 판매
            gain += cnt * arr[i] - cost
            cnt = 0
            cost = 0
        }
    }
    
    gain += cnt * arr[n-1] - cost
    
    print(gain)
    
}

처음에 틀련던 방법인데요. 올라가는지 내려가는지에 대한 배열을 만들고, 올라갈것이라면 사고 내려갈것이라면 팔고 하는 식으로 처리했습니다. 그러나 간과했던 것이 예를들어 1 1 3 2 100 이라고 하면 100일때 다 파는게 좋지만 제가 작성한 코드에서는 3에서 2가 될 때 팔아버리더라구요... 그래서 컨닝 + 생각을 좀 해서 아래와 같이 수정했습니다.

 

//
//  main.swift
//  BackJoon
//
//  Created by kokojong on 2023/04/04.
//
import Foundation
// 11501 주식 그리디 실2
// idea (컨닝): 뒤에서부터 탐색을 해서 최대값을 갱신해주면서 구매 판매 판단

let t = Int(readLine()!)!
for _ in 0..<t {
    let n = Int(readLine()!)!
    let arr = Array(readLine()!.split(separator: " ").map { Int(String($0))! }.reversed())
    
    var gain = 0
    var maxPrice = arr.first!
    
    for value in arr {
        if value >= maxPrice {
            maxPrice = value
        } else {
            gain += (maxPrice - value)
        }
    }
    
    print(gain)
    
}

핵심 아이디어는 뒤에서부터 오면서 제일 큰 값을 계속 갱신하며 큰 값을 기준으로 주식을 판다고 생각한 것 입니다.

❗️ 참고로 원래 components 로 했더니 계속 시간 초과가 나서 너무 킹받았던 기억이 있습니다...아무리 봐도 맞게 했는데!!!!! 맞왜틀?! 이러면서 하다가 시간을 많이 잡아먹었어요...

관련한 내용은 알아보고 제가 따로 깃헙에 정리 해봤땁니다 https://github.com/kokojong/kokojong_TIL/issues/16