[Swift] 백준 1406 에디터 - 시간복잡도에 익숙해지자

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

1406번: 에디터

해당 문제의 입력은 500,000이다

따라서 해당 문제는 O(n)의 시간복잡도로 충분히 풀 수 있다

var str = Array(readLine()!).map { String($0) }
let m = Int(readLine()!)!
var cursor = str.count

for _ in 0..<m {
    let command = readLine()!.split(separator: " ").map { String($0) }
    
    switch command[0] {
    case "L":
        if cursor > 0 {
            cursor -= 1
        }
    case "D":
        if cursor < str.count {
            cursor += 1
        }
    case "B":
        if cursor > 0 {
            str.remove(at: cursor - 1)
            cursor -= 1
        }
    case "P":
        str.insert(command[1], at: cursor)
        cursor += 1
    default: break
    }
}

let result = str.reduce("") {
    $0 + $1
}

print(result)

반복문을 한번밖에 사용하지 않았기때문에 이 코드의 시간복잡도는 O(n)일줄 알았다

하지만 시간초과로 문제를 틀렸다

 

이유를 곰곰히 생각해봤다

배열의 remove(at:) 및 insert(_:at:) 메서드는 시간복잡도가 O(n)이다

즉 위 코드의 시간복잡도는 O(n^2) 이 되는것이다

 

그래서 스택을 두개 만들어서 다시 구현을 했다

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

for _ in 0..<Int(readLine()!)! {
    let command = readLine()!
    
    switch command.first! {
    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()
        }
    case "P":
        left.append(command.last!)
    default: break
    }
}

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

배열의 append(_:) 및 removeLast() 메서드는 시간복잡도가 O(1)이다

그렇기에 위 코드가 바로 O(n) 짜리 코드인것이다

 

내가 짠 코드뿐만이 아닌 언어에 구현되있는 메서드의 시간복잡도도 고려를 해야한다