[Kotlin] 백준 1270 : 전쟁 - 땅따먹기

문제 링크

1270번: 전쟁 - 땅따먹기

---

---

문제 해설

문제 자체는 어려울게 전혀 없으나 메모리 제한이 발목을 잡는 문제다. 평소처럼 단순히 반복문만 돌리면 메모리 초과가 발생하기 때문에 각 테스트 케이스마다 수동으로 가비지 컬렉션을 수행해야 한다.(System.gc() 부분)

 

우선 병사 번호 \(N_{ij}\)의 절대값이 \(2^{31}\) 이하이므로 Int형은 사용할 수 없다. 두 가지 방법으로 풀어봤는데 하나는 Long형을 사용한 것이고, 하나는 절대값을 UInt형으로 저장하고 부호를 Byte형으로 저장하는 별도의 클래스를 작성하여 풀이한 것이다. 두 방법 모두 풀이 과정은 동일하다.

 

병사 번호가 들어올 때마다 Map에 병사 번호를 key로 하여 해당 key의 value를 1씩 증가시키고, value의 최대값과 가장 많이 나온 병사 번호를 갱신한다. 병사 번호를 모두 입력받았으면 value의 최대값이 병사의 수 / 2 초과이면 가장 많이 나온 병사 번호를 출력하고, 그 외의 경우에는 "SYJKGW"를 출력한다.

---

Code

• 클래스 사용

import java.util.StringTokenizer
import kotlin.math.abs

fun main() = with(System.`in`.bufferedReader()) {
    val sb = StringBuilder()
    val military = HashMap<Military, Int>()
    repeat(readLine().toInt()) {
        System.gc()
        val st = StringTokenizer(readLine())
        val t = st.nextToken().toInt()
        var max = 0
        var strongest: Military? = null
        repeat(t) {
            st.nextToken().also {
                val tmp = if (it.first() == '-') Military(abs(it.toInt()).toUInt(), 1.toByte()) else Military(it.toUInt(), 0.toByte())
                military[tmp] = military[tmp]?.plus(1) ?: 1
                if ((military[tmp] ?: 0) > max) {
                    max = maxOf(max, military[tmp] ?: 0)
                    strongest = tmp
                }
            }
        }
        sb.append(
            if (max > t / 2)
                when (strongest?.sign ?: 0) {
                    1.toByte() -> "-${strongest}\n"
                    else -> "${strongest}\n"
                }
            else "SYJKGW\n")
        military.clear()
    }
    println(sb)
}

class Military(var num: UInt, var sign: Byte) {
    override fun toString() = "${this.num}"
    override fun equals(other: Any?) = this.num == (other as Military).num && this.sign == other.sign
    override fun hashCode() = 31 * num.hashCode() + sign
}

• Long 사용

import java.util.StringTokenizer

fun main() = with(System.`in`.bufferedReader()) {
    val sb = StringBuilder()
    val military = HashMap<Long, Int>()
    repeat(readLine().toInt()) {
        System.gc()
        val st = StringTokenizer(readLine())
        val t = st.nextToken().toInt()
        var max = 0
        var strongest = 0L
        repeat(t) {
            st.nextToken().toLong().also {
                military[it] = military[it]?.plus(1) ?: 1
                if ((military[it] ?: 0) > max) {
                    max = maxOf(max, military[it] ?: 0)
                    strongest = it
                }
            }
        }
        sb.append(if (max > t / 2) "$strongest\n" else "SYJKGW\n")
        military.clear()
    }
    println(sb)
}

 

위 : Long 타입, 아래 : 클래스

두 방법 중에선 클래스를 사용한게 조금 더 빨랐다.