[Swift] 프로그래머스 Lv3. 표 편집 (구현)

https://programmers.co.kr/learn/courses/30/lessons/81303

코딩테스트 연습 - 표 편집

생각

간단한 Row 노드를 만들어서 링크드 리스트로 구현했다.

숫자 num과 앞의 노드 숫자 prev, 뒤의 노드 숫자 next, 현재 표에 들어가 있는지 체크하는 isTable 변수

만약 범위를 벗어나는 숫자 (맨 앞의 앞, 맨 뒤의 뒤) 면 -1로 두었다.

나머지는 조건대로 구현

 

테스트 1, 2, 3, 4 시간초과

효율성 테스트에서 시간초과가 났었는데

원래는 result 문자열에 O, X를 더해주는 식으로 코드를 짰었다.

var result = ""
for row in table {
    result += row.isTable ? "O" : "X"
}

근데 이게 시간초과가 나고 insert 문으로 바꿔주었더니 해결되었다.

var result = ""
for row in table {
    result.insert(row.isTable ? "O" : "X", at: result.endIndex)
}

왜..?

 

+=(_:_:)

https://developer.apple.com/documentation/swift/string/2965662

Complexity: O(m), where m is the length of the right-hand-side argument.

오른쪽 argument 의 길이가 m

 

insert(_:at:)

https://developer.apple.com/documentation/swift/string/3018525-insert

Complexity: O(n), where n is the length of the string.

문자열의 길이 n

 

 

둘다 O 아니면 X 를 더해서 똑같은ㄷ..ㅔ

음...?!

 

 

 

 

전체코드

import Foundation

var table: [Row] = []
var deleteRow: [Int] = []
var cur: Int = 0

struct Row {
    let num: Int
    var prev: Int, next: Int
    var isTable: Bool
    init(_ num: Int, _ prev: Int, _ next: Int) {
        self.num = num
        self.prev = prev
        self.next = next
        self.isTable = true
    }
}

func command_U(_ num: Int) {
    for _ in 0..<num {
        cur = table[cur].prev
    }
}

func command_D(_ num: Int) {
    for _ in 0..<num {
        cur = table[cur].next
    }
}

func command_C() {
    let prev = table[cur].prev
    let next = table[cur].next
    if prev != -1 { table[prev].next = next }
    if next != -1 { table[next].prev = prev }
    table[cur].isTable.toggle()
    deleteRow.append(cur)
    cur = table[cur].next == -1 ? table[cur].prev : table[cur].next
}

func command_Z() {
    guard let num = deleteRow.last else { return }
    deleteRow.removeLast()
    table[num].isTable.toggle()
    let prev = table[num].prev
    let next = table[num].next
    if prev != -1 { table[prev].next = num }
    if next != -1 { table[next].prev = num }
}

func solution(_ n: Int, _ k: Int, _ cmd: [String]) -> String {
    for i in 0..<n {
        if i == n-1 { table.append(Row(i, i-1, -1)) }
        else { table.append(Row(i, i-1, i+1)) }
    }
    cur = k
    
    for command in cmd {
        switch command[command.startIndex] {
        case "U":
            let split = command.split(separator: " ")
            command_U(Int(split[1])!)
        case "D":
            let split = command.split(separator: " ")
            command_D(Int(split[1])!)
        case "C":
            command_C()
        case "Z":
            command_Z()
        default:
            break    
        }
    }
    
    var result = ""
    for row in table {
        result.insert(row.isTable ? "O" : "X", at: result.endIndex)
    }
    
    return result
}