프로그래밍

https://www.acmicpc.net/problem/1406

[난이도] Silver3
[유형] 스택

[풀이]
Left Stack와 Right Stack 두가지 스택을 이용하여 문제를 해결하면 된다.
커서를 우측으로 옮길때는 Left stack의 top을 Right stack으로,
그 반대는 Right stack의 top를 Left stack으로,
커서에 문자를 추가하거나 제거할때는 Left stack에 추가,제거

LinkedList를 이용해도 삽입,제거 연산이 O(1)이므로 문제를 시간내에 풀 수 있다.
Kotlin에서 List가 아닌 LinkedList를 사용해야한다.

[스택 풀이]

  
import java.io.BufferedReader
import java.io.InputStreamReader
import java.util.*

fun main() = with(BufferedReader(InputStreamReader(System.`in`))){
    var s = readLine()
    val lst = Stack<Char>()
    var rst = Stack<Char>()
    for(a in s) lst.push(a)
    for(i in 1..readLine().toInt()) {
        var ip = readLine().split(' ')
        when (ip[0]) {
            "L" -> if(!lst.empty()) rst.push(lst.pop())
            "D" -> if(!rst.empty()) lst.push(rst.pop())
            "B" -> if(!lst.empty()) lst.pop()
            else -> {
                lst.push(ip[1][0])
            }
        }
    }
    println(lst.toCharArray()+rst.toCharArray().reversed())
}

[LinkedList 풀이]

import java.io.BufferedReader
import java.io.InputStreamReader
import java.lang.StringBuilder
import java.util.*

fun main() = with(BufferedReader(InputStreamReader(System.`in`))){
    var s = readLine()
    var list = LinkedList<Char>()
    for(a in s) list.add(a)
    var it = list.listIterator()
    while(it.hasNext()) it.next()
    var n = readLine().toInt()
    for(i in 1..n) {
        var ip = readLine().split(' ')
        when (ip[0]) {
            "L" -> if (it.hasPrevious()) it.previous()
            "D" -> if (it.hasNext()) it.next()
            "B" -> {
                if (it.hasPrevious()) {
                    it.previous()
                    it.remove()
                }
            }
            else -> it.add(ip[1][0])
        }
    }
    println(list.toCharArray())
}

https://github.com/has2/Problem-Solving/blob/master/boj-solved.ac/Silver3/1406.cpp