1406번: 에디터

문제 풀이 아이디어

처음에는 문자열을 배열로 저장하고 커서의 위치를 index로 추적해가면서 문제를 풀려고 했습니다만 이렇게 하는 경우 커서를 이동하는 경우는 문제가 없습니다만 문자를 삭제하거나 문자를 입력하는 경우에 시간 복잡도가 O(n)입니다. 🚫 입력이 최대 500,000개이므로 시간초과가 날 가능성이 높습니다.

그렇다면 무조건 입력이 O(1)인 자료형을 활용해야 합니다. 또한 순서를 저장할 수 있어야 하므로 hash table은 안됩니다. 그렇다면 사용할 수 있는 자료형은 stack이나 queue가 있습니다. queue를 활용하는 방법도 있겠습니다만 커서의 위치가 맨앞 혹은 맨뒤일 때 예외처리가 쉽지 않습니다.

따라서 이 문제를 풀 때는 Stack 2개를 이용해서 풀어보겠습니다. 각각의 Stack은 커서 좌측에 있는 문자열과 우측에 있는 문자열입니다. 좌측에는 문자열의 순서대로 저장하고 우측에는 문자열의 역순으로 저장하면 모든 명령어를 O(1)로 처리할 수 있습니다.

풀이

Array를 활용해서 Stack을 구현한 풀이

Swift에서는 Stack을 사용해서 구현합니다.

// 에디터

// 커서의 좌측, 우측에 있는 문자를 저장할 stack을 선언 (Array 활용)
var left = readLine()!.map { $0 }
var right = [Character]()

let N = Int(readLine()!)!

// 각 명령어마다 수행할 동작을 정의
//✅ 커서 왼쪽으로 이동
func moveLeft() {
    guard !left.isEmpty else { return } // 왼쪽에 더 이상 문자가 없으면 무시
    right.append(left.popLast()!) // 오른쪽으로 문자 하나 이동
    
}

//✅ 커서 오른쪽으로 이동
func moveRight() { //
    guard !right.isEmpty else { return } // 오른쪽에 문자 없으면 무시
    left.append(right.popLast()!) // 왼쪽으로 문자 하나 이동
}

//✅ 삭제
func delete() {
    guard !left.isEmpty else { return } // 왼쪽에 문자 없으면 무시
    _ = left.popLast()! // 왼쪽에서 문자 하나 제거
}

//✅ 문자 입력
func insert(_ s: Character) {
    left.append(s) //👉 왼쪽에 문자 입력
}

// 명령어 받기
for _ in 0..<N {
    let command = readLine()!
    switch command {
    case "L":
        moveLeft()
        continue
    case "D":
        moveRight()
        continue
    case "B":
        delete()
        continue
    default:
        insert(command.last!)
    }
}

// stack 두 개 합치기 (오른쪽 문자열은 거꾸로)
let result = left + right.reversed()

// 합쳐서 출력 (joined는 [String]만 가능)
print(result.map { String($0) }.joined(separator: ""))

그냥 String으로 푼 경우

사실 String의 역시 O(1)의 append와 popLast를 제공합니다. 따라서 Array로 바꾸지 않고 String 그대로 사용해도 무방합니다.

// 에디터

// 커서의 좌측, 우측에 있는 문자를 저장할 stack을 선언 (Array 활용)
var left = readLine()!
var right = ""

let N = Int(readLine()!)!

// 각 명령어마다 수행할 동작을 정의
//✅ 커서 왼쪽으로 이동
func moveLeft() {
    guard !left.isEmpty else { return } // 왼쪽에 더 이상 문자가 없으면 무시
    right.append(left.popLast()!) // 오른쪽으로 문자 하나 이동
    
}

//✅ 커서 오른쪽으로 이동
func moveRight() { //
    guard !right.isEmpty else { return } // 오른쪽에 문자 없으면 무시
    left.append(right.popLast()!) // 왼쪽으로 문자 하나 이동
}

//✅ 삭제
func delete() {
    guard !left.isEmpty else { return } // 왼쪽에 문자 없으면 무시
    _ = left.popLast()! // 왼쪽에서 문자 하나 제거
}

//✅ 문자 입력
func insert(_ s: Character) {
    left.append(s) //👉 왼쪽에 문자 입력
}

// 명령어 받기
for _ in 0..<N {
    let command = readLine()!
    switch command {
    case "L":
        moveLeft()
        continue
    case "D":
        moveRight()
        continue
    case "B":
        delete()
        continue
    default:
        insert(command.last!)
    }
}

// stack 두 개 합치기 (오른쪽 문자열은 거꾸로)
print(left + right.reversed())

❗️ 시간 초과 Case!

split(separator: )

각 명령어를 받을 때 별 생각 없이 아래의 코드를 활용하는 경우가 있을 수 있습니다.

let command = readLine()!.split(separator: " ")

하지만 위 코드는 상당히 리소스를 많이 잡아먹는 동작입니다. 처음에 한번 정도 입력을 받을 때 사용하는 것은 상관 없지만 반복문 안에서는 사용하지 맙시다!