[Chapter14, 15] - 노드 기반 자료 구조, 이진 탐색 트리로 속도 향상

[wolfy916]

연결리스트를 활용한 문제 풀이

• 백준 문제 링크

/**
 * 에디터
 * 실버2
 * 연결리스트
 * */

class Node<T>(
    var data: T,
    var prevNode: Node<T>? = null,
    var nextNode: Node<T>? = null
)

class DoublyLinkedList<T>(
    dataList: List<T>? = null
) {
    init { dataList?.let { addNodeList(it) } }

    /**
     * _cursorNode에 따른 커서 위치
     * null -> 맨 앞
     * Node -> 해당 노드 오른쪽
     * */
    private var _headNode: Node<T>? = null
    private var _cursorNode: Node<T>? = null

    /**
     * 리스트를 연결리스트화
     * */
    private fun addNodeList(list: List<T>) {
        if (list.isEmpty()) return

        if (_headNode == null) _headNode = Node(list.first())
        var currentNode = _headNode
        var prevNode: Node<T>

        var idx = 0
        while (++idx < list.size) {
            prevNode = currentNode!!
            currentNode = Node(list[idx], prevNode)
            prevNode.nextNode = currentNode
        }

        _cursorNode = currentNode
    }

    /**
     * 명령어 실행
     * */
    fun processCommand(command: String) {
        when (command.first()) {
            'L' -> moveLeftCursor()
            'D' -> moveRightCursor()
            'B' -> deleteAtCursor()
            'P' -> addAtCursor(command.last() as T)
        }
    }

    /**
     * 커서 왼쪽으로 이동
     * */
    private fun moveLeftCursor() {
        if (_cursorNode == null) return
        _cursorNode = _cursorNode?.prevNode
    }

    /**
     * 커서 오른쪽으로 이동
     * */
    private fun moveRightCursor() {
        if (_cursorNode?.nextNode == null) return
        _cursorNode = _cursorNode?.nextNode
    }

    /**
     * 커서 좌측 노드 삭제
     * */
    private fun deleteAtCursor() {
        if (_cursorNode == null) return
        val isFirstDelete = _cursorNode?.prevNode == null
        val nextNode = _cursorNode?.nextNode
        if (isFirstDelete) _headNode = nextNode
        _cursorNode = _cursorNode?.prevNode
        _cursorNode?.nextNode = nextNode
    }

    /**
     * 커서 좌측에 노드 추가
     * */
    private fun addAtCursor(data: T) {
        val isFirstAdd = _cursorNode == null
        val currentNode = _cursorNode
        val nextNode = if (isFirstAdd) _headNode else _cursorNode?.nextNode

        val newNode = Node(data, currentNode, nextNode)
        if (isFirstAdd) _headNode = newNode

        currentNode?.nextNode = newNode
        nextNode?.prevNode = newNode

        _cursorNode = newNode
    }

    override fun toString(): String {
        var result = ""
        var currentNode = _headNode
        while (currentNode != null) {
            result += currentNode.data
            currentNode = currentNode.nextNode
        }
        return result
    }
}

fun solution(sentence: String, commands: List<String>): String {
    val doublyLinkedList = DoublyLinkedList(sentence.toList())
    commands.forEach {doublyLinkedList.processCommand(it) }
    return doublyLinkedList.toString()
}

fun main() = with(System.`in`.bufferedReader()) {
    val sentence = readLine()
    val numberOfCommands = readLine().toInt()
    val commands = List(numberOfCommands) { readLine() }
    println(solution(sentence, commands))
}

• 시간초과는 StringBuilder 안써서 그런듯