백준 - 주식(Swift)

백준 - 주식(Swift)

 

 

 문제 설명

 

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

11501번: 주식

 

 나의 풀이

 

이 문제를 풀 때 간과했던 게 두 가지 있다.

1. 앞에서부터 탐색하면서 주식의 값이 떨어지는 시점에서 구입한 걸 다 파는 것을 그리디로 채택한 점.

2. 입력이 100,000이상인데 readLine을 사용하려 했다는 점.

 

이 두 가지가 풀이를 조금 느리게했다.

보통 이런 그리디 문제는 앞 인덱스와 뒤 인덱스만 참조하는 것이 아니라 max값을 설정해두고 max에따라서 문제를 해결하는 경우가 많은 것 같다. 이 문제도 그렇다. 

예를 들어

1 1 3 1 4 2라는 입력값이 주었다고 가정해보자.

처음 나의 논리라면 3에서 1이되는 시점에서 앞에 산 주식들을 팔아야한다. 하지만 최적의 이득은 4에 파는 게 맞다. 

그렇기 때문에 앞에있는 날들의  주식이 값이 뒤에서 가장 최고의 값에 팔려야한다는 아이디어가 떠오른다.

 

이는 뒤에서부터 탐색하면 쉽게 해결할 수 있다. 맨뒤의 값은 max의 값이다. (뒤에 아무것도 없기 때문에) 그리고 더 큰 값이나오면 max를 초기화해주고 더 작은 값이 나온다면 max값으로 판매한 값을 누적하면 된다. 

 

그리고 fileIO를 사용할때 공백을 기준으로 배열을 받을때는 array를 정의해둔 뒤 카운트만큼 arr.append(fIO.readInt())를 하면 된다.

 

import Foundation


final class FileIO {
    private let buffer:[UInt8]
    private var index: Int = 0

    init(fileHandle: FileHandle = FileHandle.standardInput) {
        
        buffer = Array(try! fileHandle.readToEnd()!)+[UInt8(0)] // 인덱스 범위 넘어가는 것 방지
    }

    @inline(__always) private func read() -> UInt8 {
        defer { index += 1 }

        return buffer[index]
    }

    @inline(__always) func readInt() -> Int {
        var sum = 0
        var now = read()
        var isPositive = true

        while now == 10
                || now == 32 { now = read() } // 공백과 줄바꿈 무시
        if now == 45 { isPositive.toggle(); now = read() } // 음수 처리
        while now >= 48, now <= 57 {
            sum = sum * 10 + Int(now-48)
            now = read()
        }

        return sum * (isPositive ? 1:-1)
    }

    @inline(__always) func readString() -> String {
        var now = read()

        while now == 10 || now == 32 { now = read() } // 공백과 줄바꿈 무시
        let beginIndex = index-1

        while now != 10,
              now != 32,
              now != 0 { now = read() }

        return String(bytes: Array(buffer[beginIndex..<(index-1)]), encoding: .ascii)!
    }

    @inline(__always) func readByteSequenceWithoutSpaceAndLineFeed() -> [UInt8] {
        var now = read()

        while now == 10 || now == 32 { now = read() } // 공백과 줄바꿈 무시
        let beginIndex = index-1

        while now != 10,
              now != 32,
              now != 0 { now = read() }

        return Array(buffer[beginIndex..<(index-1)])
    }
}

import Foundation

let fIO = FileIO()

let tc = fIO.readInt()

for _ in 0..<tc {
    let n = fIO.readInt()
    var sum = 0
    var arr = [Int]()
    for _ in 0..<n {
        arr.append(fIO.readInt())
    }
    arr.reverse()
    var max = 0
    for x in arr {
        if x > max {
            max = x
        } else {
            sum += max-x
        }
    }
    print(sum)
}