백준 28070: 유니의 편지 쓰기 [Kotlin 코틀린 / 누적합]

백준 28070: 유니의 편지 쓰기

😋 문제 분석

미필 N명의 복무 기간이 YYYY-MM 형태로 주어진다. (1 <= N <= 100,000)
단 한달만 편지를 써줄 것이기 때문에,
가장 많은 미필이 존재하는 구간을 구해야 한다.

✅ 문제 풀이

N이 100,000으로 상당히 크다
즉, 단순히 모든 경우를 따지는 방식은 불가능 하다.

처음에는 하나의 배열에 각 기간을 모두 기록하는 풀이법을 생각해봤었다.
YYYY-MM 형태를 적당한 다른 데이터로 변환한 다음, 배열에 기록하는 것이다.
아래 처럼 예제 입력 1 이라면

4
2023-02 2023-04
2023-03 2025-03
2023-04 2025-02
2024-02 2026-02

2023-02, 2023-03, 2023-04를 배열에 기록하고,
다음으로는 2023-03, 2023-04, ..., 2025-02, 2025-03 을 기록할 것이다.
하지만 복무기간의 범위는 2000-01 부터 9999-12 까지 가능하다.
만약 2000-1 9999-12 라는 값이 100,000개 입력된다면,
문제는 1초 내에 해결되지 않는다.

즉 O(N)이나 O(NlogN) 시간 복잡도를 갖는 알고리즘을 생각해볼 필요가 있다.
이 시점에서 적용해볼 수 있는 알고리즘이 누적합이다.
입력받은 값 이외의 데이터를 추가 기록할 필요가 없다.

우선 입력을 받자
입력받은 YYYY-MM 데이터를 하나의 정수 값으로 변환할 것이다.
연도에 12를 곱해서 단위를 달로 변경하자.
보통 누적합 배열을 사용할 때 0번째 인덱스는 비워두므로,
입력 데이터에서 차감할 YYYY-MM 값은 1999-12로 설정한다.

const val START = 1999 * 12 + 12
const val END = 9999 * 12 + 12

// 연도와 달 -> 연도*12 + 달
val monthRetuner: (Int, Int) -> Int = { y, m ->
    y * 12 + m
}

val N = readLine().toInt()
val S = IntArray(END - START + 1).apply { // 1번 인덱스가 2000-01
	...
}

입력 받는 복무 기간의 시작과 끝을 기록할 것이다.
복무 기간의 시작을 한번 카운트 하고,
복무 기간의 끝의 다음 달에 한번 카운트 한다.
이렇게 하고 누적합 배열을 만들면 복무 기간 만큼의 구간을 기록할 수 있게 된다.
일단 코드를 보자.

...
val S = IntArray(END - START + 1).apply {
    repeat(N) {
        readLine().split(" ").map { it.split("-").map(String::toInt) }
                .let {
                	// 변수 S에 복무 기간의 시작을 기록한다.
                    this[monthRetuner(it.first()[0], it.first()[1]) - START]++
					// 변수 S에 복무 기간 끝의 다음 달을 기록한다. (9999-12의 다음 달은 없으니 제외)
                    if ((it.last()[0] == 9999 && it.last()[1] == 12).not())
                        this[monthRetuner(it.last()[0], it.last()[1]) - START + 1]-- // 군필 됐다는 의미로 미필 인원 1 차감
                }
        }
    }.also {
    	// 누적합 배열만들기. 선형 탐색해가면서 미필 인원을 누적 시킨다.
        for (i in 1..(END - START)) {
            it[i] += (it[i - 1])
        }
    }
...

위와 같이 누적합 배열을 만들면 어느 기간에 미필이 가장 많은지 찾아낼 수 있다.
변수 S에게서 최대 미필 구간을 찾아낸다.

// S의 인덱스 => 특정 시점이기 때문에, 값이 가장 큰 지점의 인덱스를 얻어낸다.
val answer = (S.withIndex().maxBy { it.value }.index + START).run {
	// 연도에 12를 곱한 뒤 달을 더했기 때문에, 거꾸로 돌려낸다.
    // 값에서 12를 나눈 몫이 연도이고, 12로 나눈 나머지가 달이다. (물론 12는 12로 나누면 나머지가 0이 되기 때문에 후처리 필요)
    Pair(div(12), mod(12).toString().padStart(2, '0')) // 답의 규격을 맞추기 위해 한자리 수라면 padStart 함수로 앞에 0을 붙여준다.
}

얻어낸 값의 달이 0이라면 12월이라는 뜻이기 때문에 12로 바꿔주고, 연도에서 1을 빼준다
출력하면 정답.

if (answer.second != "00")
    print("${answer.first}-${answer.second}")
else
    print("${answer.first-1}-12")

오랜만에 누적합을 만나서 곧바로 누적합을 생각해내지는 못했다. 문제를 골고루 풀자