[알고리즘 연습] 표 편집 (프로그래머스 lv3, 스위프트)

문제

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

코딩테스트 연습 - 표 편집

풀이1 (시간초과)

func solution(_ n:Int, _ k:Int, _ cmd:[String]) -> String {

    var arr = Array(repeating: true, count: n)

    var index = k
    var stack = [Int]()

    for ca in cmd {
        let c = ca.map { String($0) }
        if c[0] == "U" {
            var count = Int(c[2..<c.count].joined())!
            while count > 0 {
                index -= 1
                if index == -1 { index = n-1 }
                if arr[index] { 
                    count -= 1 
                }
            }
        } else if c[0] == "D" {
            var count = Int(c[2..<c.count].joined())!
            while count > 0 {
                index = (index + 1) % n
                if arr[index] { 
                    count -= 1 
                }
            }
        } else if c[0] == "C" {
            arr[index] = false
            stack.append(index)
            var direction = 1
            var temp = index
            while arr[temp] == false {
                temp += direction
                if temp == n {
                    direction = -1
                    temp = index
                }
            }
            index = temp
        } else if c[0] == "Z" {
            let now = stack.removeLast()
            arr[now] = true
        }
    }

    return arr.map { $0 ? "O" : "X" }.joined()
}

• 배열을 기반으로 존재여부를 관리하는 방법
• 이동 혹은 삭제를 수행할 때 접근하는 곳이 false일 경우 빈값이므로 skip해야함
• 정석적인 풀이 방법이지만, skip하는 시간 때문에 시간초과가 발생

풀이2 (통과)

func solution(_ n:Int, _ k:Int, _ cmd:[String]) -> String {

    var arr = Array(repeating: [Int](), count: n)

    for i in 0..<n {
        arr[i] = [i-1, i+1, 1]
    }
    arr[0][0] = n-1
    arr[n-1][1] = 0

    var index = k
    var stack = [Int]()

    for c in cmd {
        let c = c.components(separatedBy: " ")
        if c[0] == "U" {
            for _ in 1...Int(c[1])! {
                index = arr[index][0]
            }
        } else if c[0] == "D" {
            for _ in 1...Int(c[1])! {
                index = arr[index][1]
            }
        } else if c[0] == "C" {
            stack.append(index)
            arr[index][2] = 0
            let pre = arr[index][0]
            let nxt = arr[index][1]
            arr[pre][1] = nxt
            arr[nxt][0] = pre
            index = nxt == 0 ? pre : nxt
        } else if c[0] == "Z" {
            let now = stack.removeLast()
            let pre = arr[now][0]
            let nxt = arr[now][1]
            arr[now][2] = 1
            arr[pre][1] = now
            arr[nxt][0] = now
        }
    }
    return arr.map { $0[2] == 1 ? "O" : "X" }.joined()
}

• 연결리스트를 활용한 풀이방법이다.
• 직접 연결리스트 구조를 구현하지는 않았고, 배열을 통해 간이 연결리스트를 구현했다. ( [이전노드의 인덱스, 다음노드의 인덱스, 존재여부] )
• 이렇게되면 false를 skip하는데 사용되는 시간이 훨씬 줄어든다.