[백준] 11501번: 주식 - Kotlin[코틀린]

문제

 

11501번: 주식

 

---

풀이

 

 단순하게 2중 for문을 사용하여 판매의 최대값을 갱신해가며 계산하는 풀이는 시간초과가 발생한다. 대신 역방향 탐색을 활용하여 해결해야 한다.

 

 주식으로 최대의 이익을 보려면 주식을 구입한 가격과 판매하는 가격의 차이가 가장 커야 한다. 역방향 탐색을 통해 판매하는 가격의 최대값을 얻을 수 있다. 먼저 마지막으로 입력받은 가격을 최대값으로 설정하고 역방향 탐색을 시작한다. 탐색 중 현재 값이 최대값보다 작다면 둘의 차이가 얻을 수 있는 가장 큰 이익이다. 현재 값이 최대값보다 크다면 최대값을 갱신해준다.

 

 예를 들어 예제 입력1에서 [1, 1, 3, 1, 2] 의 경우, 최대값을 2로 설정하고 역방향 탐색을 시작한다. 1은 2보다 작기 때문에 2원에 판매하는 것이 최대값으로 판매하는 것이다. 그 다음 만나는 값은 3이므로 3으로 최대값을 갱신해준다. 그리고 이전 주식의 값들은 3원에 판매된다.

 

---

코드

 

fun main() {
    val br = System.`in`.bufferedReader()
    val bw = System.out.bufferedWriter()

    val sb = StringBuilder()

    repeat(br.readLine().toInt()) {
        val day = br.readLine().toInt()
        val arr = br.readLine().split(' ').map { it.toInt() }

        var sum = 0L
        var max = arr[day-1]

        for(i in day-2 downTo 0) {
            if(arr[i] < max) {
                sum += max - arr[i]
            } else {
                max = arr[i]
            }
        }

        sb.append("$sum\n")
    }

    bw.write(sb.toString())
    bw.flush()
    bw.close()
    br.close()
}