라이브스마트

코틀린(Kotlin)은 현대적이고 간결한 문법과 강력한 기능 덕분에 최근 많은 개발자들 사이에서 사랑받고 있는 프로그래밍 언어입니다. 코딩 테스트, 즉 알고리즘 문제 풀이에서도 코틀린은 그 유용함을 발휘합니다. 이번 포스트에서는 코틀린을 사용하여 절댓값 힙(Absolute Value Heap)을 구현하는 방법에 대해 상세히 설명하고자 합니다.

문제 설명

절댓값 힙의 정의는 다음과 같습니다:

절댓값 힙은 항상 절댓값이 가장 작은 값을 상단에 두는 우선순위 큐(Priority Queue)입니다.
만약 절댓값이 같은 값이 여러 개 존재하는 경우, 그 값 중 실제 값이 더 작은 것을 우선시합니다.

힙의 연산은 다음과 같습니다:

• INSERT X: 정수 X (우선순위 큐에 추가)
• EXTRACT: 절댓값이 가장 작은 정수 삭제 후 출력

입력 형식

프로그램의 입력은 여러 줄로 주어지며, 각 줄에 대한 명령이 포함되어 있습니다.
각 줄은 ‘INSERT X’ 또는 ‘EXTRACT’ 형태로 주어집니다.

출력 형식

‘EXTRACT’ 명령이 호출될 때마다 출력된 값이 한 줄에 출력됩니다.

예제

    INPUT:
    INSERT -5
    INSERT 3
    INSERT -1
    EXTRACT
    EXTRACT
    INSERT -2
    EXTRACT
    EXTRACT
    EXTRACT
    

OUTPUT:
-1
-2
3

문제 분석

주어진 문제를 해결하기 위해 우리는 다음을 고려해야 합니다:

• 우선순위 큐(Priority Queue)를 어떻게 구성할 것인가?
• Java의 힙 구조를 활용할까? 아니면 코틀린의 컬렉션을 활용할까?
• 절댓값에 따라 정렬하는 방법은 무엇인가?

절댓값 힙을 만들기 위해서는 최소 힙(min-heap) 구조를 사용할 수 있습니다.
자바에서는 PriorityQueue를 사용하여 이를 쉽게 구현할 수 있습니다.
코틀린에서도 이를 활용할 수 있으며, 기본적인 힙 구조를 통해 우리가 원하는 기능을 구현할 수 있습니다.

구현 과정

1. 데이터 구조 정의

절댓값 힙에서 가장 핵심적인 부분은 데이터를 저장하는 방법입니다.
우리는 절댓값을 기준으로 정렬해야 하므로, PriorityQueue를 활용하여 요소를 추가하고 제거합니다.
요소를 추가할 때는 절댓값과 원래 값을 함께 설정해주는 것이 좋습니다.

2. Comparator 정의

PriorityQueue에서 우선순위를 정의하기 위해 커스텀 정렬 규칙(Comparator)을 정의합니다.
여기서는 절댓값이 작은 값이 먼저 와야 하며, 절댓값이 같을 경우 실제 값이 더 작은 값을 우선시해야 합니다.

    val comparator = Comparator> { a, b ->
        if (Math.abs(a.first) == Math.abs(b.first)) {
            a.first.compareTo(b.first)
        } else {
            Math.abs(a.first).compareTo(Math.abs(b.first))
        }
    }
    

3. 명령 처리

입력된 명령을 처리하기 위해 루프를 실행합니다.
명령이 INSERT X일 경우 힙에 값을 추가하고, EXTRACT 명령일 경우 힙에서 값을 제거하고 출력합니다.

    val priorityQueue = PriorityQueue>(comparator)

    val reader = BufferedReader(InputStreamReader(System.`in`))
    val n = reader.readLine().toInt()
    
    repeat(n) {
        val command = reader.readLine().split(" ")
        when (command[0]) {
            "INSERT" -> {
                val value = command[1].toInt()
                priorityQueue.add(Pair(value, value))
            }
            "EXTRACT" -> {
                if (priorityQueue.isNotEmpty()) {
                    println(priorityQueue.poll().first)
                } else {
                    println(0)
                }
            }
        }
    }
    

전체 코드

    import java.io.BufferedReader
    import java.io.InputStreamReader
    import java.util.PriorityQueue

    fun main() {
        val comparator = Comparator> { a, b ->
            if (Math.abs(a.first) == Math.abs(b.first)) {
                a.first.compareTo(b.first)
            } else {
                Math.abs(a.first).compareTo(Math.abs(b.first))
            }
        }

        val priorityQueue = PriorityQueue>(comparator)

        val reader = BufferedReader(InputStreamReader(System.`in`))
        val n = reader.readLine().toInt()

        repeat(n) {
            val command = reader.readLine().split(" ")
            when (command[0]) {
                "INSERT" -> {
                    val value = command[1].toInt()
                    priorityQueue.add(Pair(value, value))
                }
                "EXTRACT" -> {
                    if (priorityQueue.isNotEmpty()) {
                        println(priorityQueue.poll().first)
                    } else {
                        println(0)
                    }
                }
            }
        }
    }
    

결론

절댓값 힙을 구현하는 것은 동적 데이터 구조의 중요한 부분으로, 다양한 문제 해결에 도움을 줄 수 있습니다.
이번 강좌를 통해 코틀린에서 간단하고 효과적으로 힙을 구현하는 방법을 배웠습니다.
알고리즘 문제를 풀 때, 문제의 본질을 이해하고 효율적인 데이터 구조를 선택하는 것이 얼마나 중요한지를 느낄 수 있었기를 바랍니다.
앞으로도 다양한 알고리즘 문제를 함께 풀어보며 실력을 향상시켜 나가길 기대합니다!