<백준> 24.05.27에 푼 문제들

1. 주식(Silver 2)

[백준]

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

[깃허브]

ForCodeKata/baekjoon 문제집/주식 at main · heesoo-park/ForCodeKata

제출 결과

작성한 코드는 다음과 같다.

import java.io.*
import java.util.*

private val br = BufferedReader(InputStreamReader(System.`in`))

fun main(args: Array<String>) {
    val bw = BufferedWriter(OutputStreamWriter(System.out))

    val t = br.readLine().toInt()
    repeat(t) {
        bw.write("${getMaxBenefit()}\n")
    }

    bw.flush()
    bw.close()
}

fun getMaxBenefit(): Long {
    val n = br.readLine().toInt()
    val stocks = br.readLine().split(' ').map { it.toInt() }
    var result: Long = 0

    var max = stocks[n - 1]
    for (i in n - 2 downTo 0) {
        if (max > stocks[i]) {
            result += (max - stocks[i])
        } else {
            max = stocks[i]
        }
    }

    return result
}

(계속 앞에서부터 순회하는 방법만 쓰다가 뒤로 해보니까 바로 해결됨...)

(앞에서부터 하면 O(N^2) 나오고, 뒤에서부터 하면 O(N))

 

2. 창고 다각형(Silver 2)

[백준]

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

[깃허브]

ForCodeKata/baekjoon 문제집/창고 다각형 at main · heesoo-park/ForCodeKata

제출 결과

작성한 코드는 다음과 같다.

import java.io.*
import java.util.*

// 기둥 정보 저장하는 data class
data class Pillar(
    val pos: Int,
    val height: Int
) {
    companion object {
        fun makePillar(list: List<Int>) = Pillar(list[0], list[1])
    }
}

fun main(args: Array<String>) {
    val br = BufferedReader(InputStreamReader(System.`in`))
    val bw = BufferedWriter(OutputStreamWriter(System.out))
    
    val n = br.readLine().toInt()
    val storage = mutableListOf<Pillar>()
    val stack = Stack<Pillar>()
    var result = 0
    
    // 1. 기둥 저장
    repeat(n) {
        storage.add(Pillar.makePillar(br.readLine().split(' ').map { it.toInt() }))
    }
    
    // 2. 기둥 정렬(위치 기준 오름차순)
    storage.sortBy { it.pos }
    
    // 3. 가장 높은 기둥의 인덱스 찾기
    var idx = 0
    for (i in storage.indices) {
        if (storage[idx].height < storage[i].height) idx = i
    }
    result += storage[idx].height
    
    // 4. 가장 높은 기둥 왼쪽 계산
    for (i in 0 until idx) {
        if (stack.isEmpty()) {
            stack.push(storage[i])
            continue
        }
        
        if (stack.peek().height < storage[i].height) {
            stack.push(storage[i])
        }
    }
    
    var prev = storage[idx]
    while (stack.isNotEmpty()) {
        val cur = stack.pop()
        result += (cur.height * (prev.pos - cur.pos))
        prev = cur
    }
    
    // 5. 가장 높은 기둥 오른쪽 계산
    for (i in storage.lastIndex downTo idx + 1) {
        if (stack.isEmpty()) {
            stack.push(storage[i])
            continue
        }
        
        if (stack.peek().height < storage[i].height) {
            stack.push(storage[i])
        }
    }
    
    prev = storage[idx]
    while (stack.isNotEmpty()) {
        val cur = stack.pop()
        result += (cur.height * (cur.pos - prev.pos))
        prev = cur
    }
    
    bw.write("$result\n")
    bw.flush()
    bw.close()
}

(왼쪽, 오른쪽 나눠서 하니까 금방 해결됐다..!)