[BOJ] 3015 오아시스 재결합 - P5

문제풀이

1. 스택에 (키, 사람 수)를 저장하고 나보다 작거나 같은 사람이 있으면 제거한다.

---

주의사항

1. 같은 키의 사람을 처리할 때 주의해야 한다.

---

소요시간

40분

---

package 백준.Platinum.P5.p3015_오아시스재결합

fun main() {
    val N = readln().toInt()
    val stack = ArrayDeque<Pair<Int, Int>>()
    var result = 0L
    repeat(N) {
        val num = readln().toInt()
        var count = 1
        while (stack.isNotEmpty() && stack.first().first <= num) {
            if (stack.first().first == num) count += stack.first().second
            result += stack.removeFirst().second
        }
        if (stack.isNotEmpty()) result++
        stack.addFirst(num to count)
    }
    println(result)
}

https://github.com/TaeGN/Algorithm/blob/master/src/%EB%B0%B1%EC%A4%80/Platinum/P5/p3015_%EC%98%A4%EC%95%84%EC%8B%9C%EC%8A%A4%EC%9E%AC%EA%B2%B0%ED%95%A9/p3015_%EC%98%A4%EC%95%84%EC%8B%9C%EC%8A%A4%EC%9E%AC%EA%B2%B0%ED%95%A9.kt

---

문제링크

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

---

회고

같은 키의 사람을 처리하는게 좀 까다로웠다.