백준 18866 젊은 날의 생이여 Kotlin (누적 합)

문제 출처 : https://www.acmicpc.net/problem/18866

18866번: 젊은 날의 생이여

문제

욱제는 입대를 앞두고 <이등병의 편지>를 부르고 있다.

… 이제 다시 시작이다 젊은 날의 생이여 … 

그런데 과연 욱제에게 젊은 날이 있었을까? 욱제에게 젊은 날이 있었는지 알아보자.

먼저, N년간 욱제의 행복도와 피로도가 주어진다. 행복도와 피로도는 양의 실수 값을 가진다. 어떤 1 ≤ K < N에 대해 1, 2, …, K년은 욱제의 젊은 날이고, K + 1, K + 2, …, N년은 욱제의 늙은 날이다.

젊은 날과 늙은 날은 다음의 조건을 만족한다:

• 임의의 젊은 날의 행복도는 임의의 늙은 날의 행복도보다 높다.
• 임의의 젊은 날의 피로도는 임의의 늙은 날의 피로도보다 낮다.

욱제는 자신의 행복도와 피로도를 이용하여 자신의 젊은 날을 알아보려 한다. 하지만, 일부 값이 누락되었다. 욱제를 도와주자.

입력

첫째 줄에 N이 주어진다.

둘째 줄부터 N개의 줄에는 두 정수 ui, vi (1 ≤ i ≤ N)가 주어진다. ui, vi가 1 이상일 경우 각각 i년의 행복도와 피로도를 나타내며, 0인 경우에는 값이 누락되었음을 의미한다.

출력

욱제의 젊은 날이 될 수 있는 최대 기간, 즉 문제의 조건을 만족할 수 있는 최대의 1 ≤ K < N을 출력한다. 단, 이러한 K가 없을 경우, -1을 출력한다.

제한

• 2 ≤ N ≤ 1,000,000
• 0 ≤ ui, vi ≤ 109
• 주어지는 N개의 행복도 중 0이 아닌 값은 모두 다르다.
• 주어지는 N개의 피로도 중 0이 아닌 값은 모두 다르다.

알고리즘 분류

• 누적 합

풀이

이 문제는 조건을 해석하여 식을 세우고, 이를 최적화할 방안을 찾아야 한다.

k를 어떤 방법으로 구할 수 있을까?

• 임의의 젊은 날의 행복도는 임의의 늙은 날의 행복도보다 높다.
• 임의의 젊은 날의 피로도는 임의의 늙은 날의 피로도보다 낮다.

이 조건을 풀어보면 젊은 날의 행복도 최솟값이 늙은 날의 행복도 최댓값보다 높아야 한다.

젊은 날의 피로도의 최댓값은 늙은 날의 피로도 최솟값보다 낮야아 한다.

그럼 K를 구하는 조건은, 임의의 날 K를 정했을 때

왼쪽 (젊은 날)의 행복 최솟값 >= 오른쪽 (늙은 날)의 행복 최댓값

왼쪽 (젊은 날)의 피로 최댓값 <= 오른쪽  (늙은 날)의 피로 최솟값

이어야 한다.

'='를 붙인 이유는 0 때문인데 일단 넘어가자.

 

그럼 N개중에 젊은 날을 최대로 가진 K를 구하는 가장 간단한 방법은 1부터 N까지 모두 K를 대입해 보면서 가장 큰 값을 K로 정하면 된다.

이 작업의 시간 복잡도는 어떻게 될까?

K를 N번 지정해야 하고, 매번 K의 왼쪽에서 행복 최소, 피로 최대, k의 오른쪽에서 행복 최대, 피로 최소를 구해야 하므로 N번 반복된다.

즉 O(N^2)의 시간 복잡도로 통과할 수 없다.

다른 방법을 알아보자.

 

K의 왼쪽 집합... 오른쪽 집합... 우리가 사용하는 값들이 연속적인 성질을 띄는 것을 알 수 있다.

우리가 필요한 것은 모든 값이 아니라 최대, 최솟값들....

누적 합이 떠오르지 않는가?!

예를 들어 젊은 날의 행복 최소, 피로 최대를 구한다고 해 보자.

1부터 K까지 행복 최소를 누적 기록하고, 피로 최대를 누적하면 된다. 

예제 1에서 K가 3이라고 예로 들면

youngGood = 5 4 3

youngBad = 1 2 3

늙은 날의 행복 최대, 피로 최소도 구해보자.

늙은 날은 K의 오른쪽으로 뒤에서부터 누적한다.

oldGood = 2 1

oldBad = 4 4

K가 3일 때 youngGood[3]이 oldGood[4]보다 크고 youngBad[3]이 oldBad[4]보다 작기 때문에 K는 3이 될 수 있다

K에 4를 넣어보면 조건이 성립하지 않는 것을 알 수 있다.

 

따라서 youngMinGood, youngMaxBad, oldMaxGood, oldMinBad의 누적 합 리스트를 만들고 이를 이용해 1부터 N까지 K를 넣어보며 가능한 가장 큰 수를 반환하면 되므로 O(N)으로 해결할 수 있다.

 

위에서 언급한 '='를 사용한 이유는 0이라는 조건이 있기 때문이다.

0은 누락된 숫자로, 우리가 임의의 수를 넣을 수 있다는 의미이다. 이는 곧 젊은 날이 많게끔 숫자를 넣을 수 있다는 것을 의미한다.

젊은 날이 유리하게 하려면 youngMinGood, youngMaxBad, oldMaxGood, oldMinBad 누적 합을 구하는 과정에서 이전 값을 그대로 사용해야 한다. 그러면 K를 정하고 젊은 날과 늙은 날을 비교할 때 두 값이 같은 경우가 있다. 이 경우는 0이 들어있단 의미로 등호를 사용하여 조건을 통과시키는 것이다. 

 

코드

val br = System.`in`.bufferedReader()
fun getIntList() = br.readLine().trim().split(' ').map { it.toInt() }
fun getStr() = br.readLine().trim()
fun getInt() = br.readLine().trim().toInt()

fun main() = with(System.out.bufferedWriter()){
    val n = getInt()
    val good = IntArray(n)
    val bad = IntArray(n)
    for(i in 0 until n){
        val (g,b) = getIntList()
        good[i] = g
        bad[i] = b
    }
    val youngMinGood = IntArray(n+2){Int.MAX_VALUE}
    val youngMaxBad = IntArray(n+2){0}
    val oldMaxGood = IntArray(n+2){0}
    val oldMinBad = IntArray(n+2){Int.MAX_VALUE}
    for(i in 1 .. n){
        youngMinGood[i] = if(good[i-1]==0) youngMinGood[i-1] else youngMinGood[i-1].coerceAtMost(good[i-1])
        youngMaxBad[i] = if(bad[i-1]==0) youngMaxBad[i-1] else youngMaxBad[i-1].coerceAtLeast(bad[i-1])
    }
    for(i in n downTo 1){
        oldMaxGood[i] = if(good[i-1]==0) oldMaxGood[i+1] else oldMaxGood[i+1].coerceAtLeast(good[i-1])
        oldMinBad[i] = if(good[i-1]==0) oldMinBad[i+1] else oldMinBad[i+1].coerceAtMost(bad[i-1])
    }
    var answer = -1
    for(i in 1 until n){
        if(youngMinGood[i] >= oldMaxGood[i+1] && youngMaxBad[i] <= oldMinBad[i+1]){
            answer = i
        }
    }
    write("$answer")
    close()
}