[BOJ] (Swift) 1406 - 에디터

1406번: 에디터

---

문제 요약

• 커서를 기준으로 하는 편집기를 만들자.

 

---

시간 초과 1

import Foundation

var arr = Array(readLine()!)
var M = Int(readLine()!)!

var index = arr.count

func P(_ x: Character) {
    arr.insert(x, at: index)
    index += 1
}

func L() {
    if index > 0 {
        index -= 1
    }
}

func D() {
    if index < arr.count {
        index += 1
    }
}

func B() {
    if index > 0 {
        arr.remove(at: index - 1)
        index -= 1
    }
}

for _ in 0..<M {
    var command = readLine()!.split{ $0 == " "}
    switch command[0] {
    case "L":
        L()
        break
    case "D":
        D()
        break
    case "P":
        P(Character(String(command[1])))
        break
    case "B":
        B()
        break
    default:
        break
    }
}

print(String(arr))

• 배열 arr에 문자열을 넣고 커서의 위치를 나타내는 변수 index로 나타냈다.
• 삽입, 삭제를 insert, remove 메서드를 사용해 구현했다. 
• 시간 초과 이유 → 시간 복잡도가 O(n)인 insert(), remove() 메서드 때문이라 생각한다. 시간 복잡도가 O(1)인 popLast()와 append()를 사용해보자.

시간 초과 2

import Foundation

var arrL = Array(readLine()!)
var arrR: [Character] = []
var M = Int(readLine()!)!


func P(_ x: Character) {
    arrL.append(x)
}

func L() {
    if !(arrL.isEmpty) {
        arrR.append(arrL.popLast()!)
    }
}

func D() {
    if !(arrR.isEmpty) {
        arrL.append(arrR.popLast()!)
    }
}

func B() {
    if !(arrL.isEmpty) {
        arrL.popLast()!
    }
}

for _ in 0..<M {
    var command = readLine()!.split{ $0 == " "}
    switch command[0] {
    case "L":
        L()
        break
    case "D":
        D()
        break
    case "P":
        P(Character(String(command[1])))
        break
    case "B":
        B()
        break
    default:
        break
    }
}

print(String(arrL) + String(arrR).reversed())

• 두 개의 배열을 이용했다. arrL은 커서 좌측 문자열, arrR은 커서 우측 문자열을 의미한다. 
• 참고로 append 연산을 사용했기 때문에 arrR은 뒤집어져 있는 상태이다. 결과를 출력할 때 reversed 연산을 사용해주자.
• 시간 초과 이유 → split 연산도 시간 복잡도 O(n)이다. ㅎㅎ

 

풀이

import Foundation

var arrL = Array(readLine()!)
var arrR: [Character] = []
var M = Int(readLine()!)!


func P(_ x: Character) {
    arrL.append(x)
}

func L() {
    if !(arrL.isEmpty) {
        arrR.append(arrL.popLast()!)
    }
}

func D() {
    if !(arrR.isEmpty) {
        arrL.append(arrR.popLast()!)
    }
}

func B() {
    if !(arrL.isEmpty) {
        arrL.popLast()!
    }
}

for _ in 0..<M {
    var command = readLine()!
    switch command {
    case "L":
        L()
        break
    case "D":
        D()
        break
    case "B":
        B()
        break
    default:
        P(command.last!)
    }
}

print(String(arrL) + String(arrR).reversed())

• split()을 사용하지 않았다.