[Kotlin] 코딩 테스트 대비 주요 알고리즘 & 함수 정리

코틀린 코테를 대비한 주요 알고리즘 & 함수를 정리합니다.

 

입출력

빠른 입력을 위해서 System.`in`.bufferdReader()를 활용합니다.

StringBuilder 와 bufferedWriter를 활용해서 빠른 출력을 사용할 수 있습니다.

fun main() = with(System.`in`.bufferedReader()) {
    val integer = readLine().toInt()

    // 공백 기준으로 분리
    val nums = readLine()
        .split(" ")
        .map { it.toInt() }

    print(integer)

    print(nums)

    val sb = StringBuilder()
    sb.append(5)
    sb.append("abc")

    print(sb)

    val bw = System.out.bufferedWriter()
    bw.flush()
    bw.close()
}

 

컬렉션 함수

추출, 집계, 필터 컬렉션 함수를 활용해서 효율적이고 간결한 처리를 할 수 있습니다.

fun main(){
    // 추출
    val list = List(6) { it * it }
    println(list.slice(1..3))
    println(list.take(2))
    println(list.drop(2))
    println(list.takeWhile { it < 10 }) // 선택 후 추출
    println(list.dropWhile { it < 10 }) // 제거 후 추출

    // 집계 함수
    val list2 = (1..5).toList()
    println(list2.reduce { acc,n -> acc + n * 2}) // 누적 값 반환
    println(list2.fold(0){ acc,n -> acc+ n*2}) // 기초값 기준으로 누적 값 반환

    // 필터
    val list3 = listOf("Red","Green","Blue")
    println(list3.filter { it.length > 3 })
    println(list3.filterNot { it.length > 3 })

}

 

배열

배열을 쉽게 생성하고, 다차원 배열을 활용할 수 있습니다.

불변과 가변 리스트를 구분하는 코틀린의 특성을 이해하고 활용할 수 있습니다.

    // 배열 쉽게 생성
    val arr1 = intArrayOf(1, 2, 3)

    val arr2 = IntArray(4) { 0 }
    val arr3 = IntArray(4) { it * 2 } //it = index

    print(arr3.contentToString())

    // 다차원 배열
    val n = 2
    val m = 3
    val arr4 = Array(n) {
        BooleanArray(m)
    }
    arr4[0][0] = true
    println(arr4[0][0])

    // 리스트

    // 불변 리스트
    val list1 = listOf(1, 2, 3)
    val list2 = mutableListOf(1, 2, 3)

    // 가변 리스트
    val list3 = List<Int>(5) { 0 }

 

스택

코틀린에서는 별도의 스택 클래스가 존재하지 않으므로, MutableList를 활용해서 이를 구현해야 합니다.

    // 스택
    // 별도의 스택 클래스가 존재하지 않음
    val stack = MutableList<Int>(4) { it } // 인덱스

    stack.add(5) // push
    stack.removeLast() // pop
    stack.last() // peek

    stack.isEmpty()
    stack.isNotEmpty()

 

큐

큐 또한 따로 존재하지 않지만, LinkedList를 활용해서 비슷한 기능을 기대할 수 있습니다.

    // 큐
    val q = LinkedList<Int>()
    q.offer(3) // push
    q.peek() // peak
    q.poll() // pop

 

덱

deque 자료구조 (덱, 디큐)를 활용해서 양방향 큐를 구현할 수 있습니다.

코틀린 자료형인 ArratyDeque를 활용합니다.

    // 덱 deque
    val deque = ArrayDeque<Int>()

    deque.addLast(1)
    deque.add(2)

    deque.removeFirst()
    deque.removeLast()

    deque.first()
    deque.last()

 

우선순위 큐

priorityQueue를 활용할 수 있습니다.

우선순위가 높은 최대 힙으로 구현되며, 파이썬과 다른점은 큰 수를 우선으로 하는 최대 힙을 적용한다는 점입니다.

// 우선순위가 높은 최대 힙
    val a = PriorityQueue<Int>()

    a.addAll(arrayOf(1,5,67,85,3,4)) // 생성
    a.offer(111) // 단일 추가

    println(a.peek()) // 가장 높은 우선순위 출력
    println(a.poll()) // 가장 높은 우선순위 pop

    val b = PriorityQueue<String> { a,b ->
        // 커스텀으로, a와 b를 비교할 때 길이를 통해 정렬한다
        a.length.compareTo(b.length)
    }
    b.addAll(arrayOf("sdf","123123","23424","z"))
    println(b) // [z,sdf,23424,123123]

 

그래프

코틀린으로 트리 구조를 쉽게 구현할 수 있습니다.

트리는 그래프의 일종이며, node와 edge로 이루어져 있습니다.

이진 트리를 구현하여 트리 순회를 적용할 수 있습니다.

data class Node(
    var value: Int,
    var left: Node? = null,
    var right: Node? = null,
)
data class Tree(val root: Node)

fun preOrderTraversal(node: Node?){
    if (node ==null) return
    print("${node.value}")
    preOrderTraversal(node.left)
    preOrderTraversal(node.right)
}

fun inOrderTraversal(node: Node?){
    if (node == null) return
    inOrderTraversal(node.left)
    print("${node.value}")
    inOrderTraversal(node.right)
}

fun postOrderTraversal(node: Node?){
    if (node == null) return
    postOrderTraversal(node.left)
    postOrderTraversal(node.right)
    print("${node.value}")
}

fun main(){
    val a = Node(1)
    val b = Node(2)
    val c = Node(3)
    val t = Tree(a)
    a.left = b
    a.right = c
    //  1
    // 2 3
    println("Pre-order Traversal:")
    preOrderTraversal(t.root)
    println()

    println("In-order Traversal:")
    inOrderTraversal(t.root)
    println()

    println("Post-order Traversal:")
    postOrderTraversal(t.root)
    println()
}