[Swift Algorithm] 에디터 BOJ #1406

문제 설명

한 줄로 된 간단한 에디터를 구현하려고 한다. 이 편집기는 영어 소문자만을 기록할 수 있는 편집기로, 최대 600,000글자까지 입력할 수 있다.

이 편집기에는 '커서'라는 것이 있는데, 커서는 문장의 맨 앞(첫 번째 문자의 왼쪽), 문장의 맨 뒤(마지막 문자의 오른쪽), 또는 문장 중간 임의의 곳(모든 연속된 두 문자 사이)에 위치할 수 있다. 즉 길이가 L인 문자열이 현재 편집기에 입력되어 있으면, 커서가 위치할 수 있는 곳은 L+1가지 경우가 있다.

이 편집기가 지원하는 명령어는 다음과 같다.

L	커서를 왼쪽으로 한 칸 옮김 (커서가 문장의 맨 앞이면 무시됨)
D	커서를 오른쪽으로 한 칸 옮김 (커서가 문장의 맨 뒤이면 무시됨)
B	커서 왼쪽에 있는 문자를 삭제함 (커서가 문장의 맨 앞이면 무시됨) 삭제로 인해 커서는 한 칸 왼쪽으로 이동한 것처럼 나타나지만, 실제로 커서의 오른쪽에 있던 문자는 그대로임
P $	$라는 문자를 커서 왼쪽에 추가함

초기에 편집기에 입력되어 있는 문자열이 주어지고, 그 이후 입력한 명령어가 차례로 주어졌을 때, 모든 명령어를 수행하고 난 후 편집기에 입력되어 있는 문자열을 구하는 프로그램을 작성하시오. 단, 명령어가 수행되기 전에 커서는 문장의 맨 뒤에 위치하고 있다고 한다.

 

입력

첫째 줄에는 초기에 편집기에 입력되어 있는 문자열이 주어진다. 이 문자열은 길이가 N이고, 영어 소문자로만 이루어져 있으며, 길이는 100,000을 넘지 않는다. 둘째 줄에는 입력할 명령어의 개수를 나타내는 정수 M(1 ≤ M ≤ 500,000)이 주어진다. 셋째 줄부터 M개의 줄에 걸쳐 입력할 명령어가 순서대로 주어진다. 명령어는 위의 네 가지 중 하나의 형태로만 주어진다.

 

출력

첫째 줄에 모든 명령어를 수행하고 난 후 편집기에 입력되어 있는 문자열을 출력한다.

 

입출력 예제

입력

abcd
3
P x
L
P y

출력

abcdyx

 

내 문제 풀이

import Foundation

var left = Array(readLine()!)
var right = [Character]()
let count = Int(readLine()!)!

for _ in 0..<count {
    let edit = readLine()!
    if edit == "L" && !left.isEmpty { right.append(left.removeLast()) }
    else if edit == "D" && !right.isEmpty { left.append(right.removeLast()) }
    else if edit == "B" && !left.isEmpty { left.removeLast() }
    else if edit.first! == "P" { left.append(edit.last!) }
}

print(String(left + right.reversed()))

• 스택을 이용하여 풀이했다.
• 커서를 기준, 왼쪽 문자를 담을 배열 left와 오른쪽 문자를 담을 배열 right를 생성했다.
• L이 입력됐을 경우 왼쪽 배열이 비었는지 체크해주고,
  비어있지 않을 경우 removeLast()를 이용하여
  left 마지막 요소를 지우는 동시에 right 마지막 자리에 추가해주었다.
• D가 입력된 경우에는 오른쪽 배열이 비었는지 체크해주고,
  비어있지 않을 경우에는 역시나 removeLast()이용하여
  right 마지막 요소를 left 마지막 자리에 추가해주었다.
• B가 입력된 경우에는 왼쪽 배열이 비었는지 체크, 왼쪽의 마지막 요소를 삭제해주었다.
• P가 입력된 경우에는 왼쪽 배열의 마지막에, 입력한 문자를 추가해주었다.
• left, right 배열을 만들지 않고 그냥 배열 하나만 생성하여
  insert, remove 등을 이용해줄 수도 있지만, 그렇게 하면 계속 배열의 모든 요소를
  한 칸씩 옮겨주는 작업을 반복해야하기 때문에 시간이 너무 오래걸린다.
  따라서 이렇게 스택을 이용했다.
  👉  처음부터 스택으로 푼 것은 아니고,, 배열로 풀었을 때 아무리 수정해도
  계속 시간초과가 떠서 스택으로 새로 풀었다. 아래는 배열로 풀었던 풀이를 첨부한다. 

 

(배열 풀이)

import Foundation

var input = Array(readLine()!).map({String($0)})
input.append(" ") // 맨 뒤에 공백 추가 (커서를 의미)

let count = Int(readLine()!)!
var edit = ""

for _ in 0..<count {
    edit = readLine()! // 명령어 입력
    if edit == "L" && input[input.startIndex] != " " { toLeft() }
    if edit == "D" && input[input.endIndex] != " " { toRight() }
    if edit == "B" && input[input.startIndex] != " " { Remove() }
    if edit.first! == "P" { Insert() }
}

print(input.joined().filter({$0 != " "}))

// 'L' 명령어 처리 함수
func toLeft() {
    let blank = input.firstIndex(of: " ")!
    input.remove(at: blank)
    input.insert(" ", at: blank - 1)
    return
}

// 'D' 명령어 처리 함수
func toRight() {
    let blank = input.firstIndex(of: " ")!
    input.remove(at: blank)
    input.insert(" ", at: blank + 1)
    return
}

// 'B' 명령어 처리 함수
func Remove() {
    let blank = input.firstIndex(of: " ")!
    input.remove(at: blank - 1)
    return
}

// 'P' 명령어 처리 함수
func Insert() {
    let blank = input.firstIndex(of: " ")!
    input.insert(String(edit.last!), at: blank)
    return
}

 

💡 피드백

• 위의 배열 풀이를 보면 알겠지만, 스택으로 푸니 훨씬 효율적이고 코드 자체도 아주 짧아진 모습을 볼 수 있다.
• 앞으로도 remove, insert 등을 반복해서 사용하는 작업은 최대한 피하는 것이 좋겠다.

 

---

 

문제

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