[Kotlin] 알고리즘을 위한 코틀린 자료구조

배열

    // 배열 초기화
    val array1 = arrayOf(1, 2, 3)
    val array2 = Array(3) {0}
    
    println(array1.joinToString())	// 1, 2, 3
    println(array2.joinToString())	// 0, 0, 0
    
    array2[0] = 1					// 0 인덱스의 값을 1로 변경
    println(array2.joinToString())	// 1, 0, 0
 
 		
    // ArrayList 생성
    val list = ArrayList<Int>() 
	
    list.add(1)
    list.add(2)
    
    println(list)	// 1, 2

 

 

스택 자료구조를 따로 가지고 있지 않으며, MutableList 인터페이스를 활용하여 스택을 구현이 가능하다

스택 - MutableList

    val stack1 = mutableListOf<Int>() 	// 빈 리스트 생성
    val stack2 = MutableList<Int>(3){0} // 0으로 초기화된 크기 3의 스택
	
    println(stack1) // []
    println(stack2) // [0, 0, 0]
    
    // 맨 끝에 1을 추가
    stack1.add(1)
    stack2.add(1)
    
    println(stack1) // [1]
    println(stack2) // [0, 0, 0, 1]
    
    println(stack1.isEmpty())		// false
    println(stack1.isNotEmpty())	// true
    
    val last = stack1.removeLast()	// 맨 끝 추출 후 리턴(pop)
    
    println(last)	// 1
    println(stack1)	// []

 

ArrayDeque를 이용하면 조금 더 빠르고 메모리 효율이 좋은 스택 자료구조를 표현할 수 있다.

스택 - ArrayDeque

    // 스택 생성
    val stack = ArrayDeque<Int>()

    // 스택에 요소 추가 (Push)
    stack.push(1)
    stack.push(2)
    stack.push(3)

    // 스택의 최상단 요소 확인
    println(stack.peek()) // 3

    // 스택에서 요소 제거 (Pop)
    println(stack.pop()) // 3
    println(stack.pop()) // 2

    // 스택의 현재 상태
    println(stack) // [1]

    // 스택이 비어 있는지 확인
    println(stack.isEmpty()) // false

 

 

큐 자료구조가 별도로 존재하지 않으며, LinkedList 인터페이스를 이용하여 구현가능

큐

    val queue = LinkedList<Int>()
    queue.offer(1) // 1
    queue.offer(2) // 2
    queue.offer(3) // 3
    println(queue) // 1, 2, 3
    
    println(queue.peek()) // 가장 앞을 리턴
    println(queue) // 1, 2, 3

    println(queue.poll()) // 가장 앞을 추출하여 리턴
    println(queue) // 2, 3

 

 

우선순위 큐의 경우, 자료구조가 존재하며, 가장 작은 값을 우선시하는 min-heap 구조가 기본이다.

큰 값을 우선하는 max-heap 구조는 Comparator를 활용해서 구현 가능하다.

우선순위 큐

	// 우선순위 큐 생성, 기본적으로 최소 힙(min-heap) 구조
    val minHeap = PriorityQueue<Int>()

    // 요소 추가
    minHeap.add(5)
    minHeap.add(1)
    minHeap.add(3)
    minHeap.add(2)

    println("우선순위 큐 상태: $minHeap") // 1, 2, 3, 5

    // 요소 제거 (가장 낮은 값)
    while (minHeap.isNotEmpty()) {
        val removedOne = minHeap.poll() // 최상위 요소 제거 및 반환
        println("제거된 값: $removedOne") // 제거된 값 출력 (1, 2, 3,5 순)
    }

    
    // max-heap을 생성하기 위해 Comparator를 사용
    val maxHeap = PriorityQueue<Int>(compareByDescending { it })

    // 요소 추가
    maxHeap.add(5)
    maxHeap.add(1)
    maxHeap.add(3)
    maxHeap.add(2)

    println("최대 힙 상태: $maxHeap") // 5, 3, 2, 1

    // 요소 제거 (가장 큰 값)
    while (maxHeap.isNotEmpty()) {
        val removedOne = maxHeap.poll() // 최상위 요소 제거 및 반환
        println("제거된 값: $removedOne") // 제거된 값 출력 (5, 3, 2, 1 순서)
    }