[백준] (Swift) 1406번 - 에디터

 

문제링크

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

1406번: 에디터

 

내가 푼 풀이 (1) - 시간초과!

• 커서를 움직여야한다는 생각으로 배열에서 인덱스를 왔다갔다 하는 방식으로 풀었음.
• 배열을 움직이고, 하나의 연산이 수행될때마다 인덱스와 문자열을 바꾸어줘야하기 때문에 시간초과가 발생한 것 같음.

import Foundation

var text = Array(readLine()!)
let n = Int(readLine()!)!


var cursor = text.count

for _ in 0..<n {
    var edit = readLine()!.components(separatedBy: " ")

    switch edit.removeFirst() {
        case "L" :
        if cursor > 0 {
            cursor -= 1
        }

        case "D" :
        if cursor != text.count {
            cursor += 1
        }

        case "B" :
        if cursor != 0 {
            text.remove(at:cursor-1)
            cursor -= 1
        }

        case "P" :
        var t = edit.popLast()!
        text.insert(contentsOf: t , at: cursor)
        cursor += 1

        default :
            break
    }

}

print(String(text))

 

내가 푼 풀이 (2) - 맞았습니다!

앞에서 배열로 문제를 풀었을 때 시간 초과가 나와서 어떻게 하면 줄일 수 있을지 생각하다가, 이전에 파이썬으로 코테 공부를 할때 deque와 같은 기본 자료구조를 이용하면 시간이 절약된다는 사실을 기억했다. 그래서 스택과 큐? 를 이용해서 어떻게 풀까, pop, remove 기능을 어떻게 이용해서 풀까 고민하다가 인터넷을 조금 서치해보았다. 

내가 이전에 배열에서 인덱스로 커서를움직였다면, pop push를 이용해서 커서를 움직이는 방식이 있었다.

[left] cursor [right] 이렇게 구조를 생각하여 커서를 왼쪽으로 움직이는 명령일때는 [left] 에서 맨 마지막 character를 [right]로 움직여주는 방식이다. 이렇게 하게 되면 배열에 따른 연산이 일어나지 않고 단순히 pop/push 동작으로만 이루어지기 때문에 훨씬 시간이 줄어드는 것 같았다. 

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

for _ in 0..<n {
    let edit = readLine()!
    switch edit {
    case "L":
        if !left.isEmpty {
            right.append(left.removeLast())
        }
    case "D" :
        if !right.isEmpty {
            left.append(right.removeLast())
        }
    case "B" :
        if !left.isEmpty {
            left.removeLast()
        }
    default:
        left.append(edit.last!)
    }
}

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

 

 

배열로 푸는 방식보다 자료구조를 활용하여 문제를 푸는 방식에 대해서 더 깊게 생각하는 시간을 가질 필요가 있을 것같다. 문제를 많이 풀면 달라지겟지? 히히