프로그래머스 - 표 편집 (Lv.3)

문제 링크

풀이

import Foundation

enum Order {
    case U(Int)
    case D(Int)
    case C
    case Z
}

var linkedList: [[Int]] = []
var selectRow = 0
var recentlyDelRows: [Int] = []

func solution(_ n:Int, _ k:Int, _ cmd:[String]) -> String {
    linkedList = (0..<n).map { i -> [Int] in [i - 1, i + 1] }
    selectRow = k
    
    let orders = cmd.map { cmdStr -> Order in
        let firstWord = cmdStr.prefix(1)
        switch firstWord {
            case "U":
                var numStr = cmdStr
                numStr.removeFirst(2)
                let num = Int(numStr)!
                return Order.U(num)
            case "D":
                var numStr = cmdStr
                numStr.removeFirst(2)
                let num = Int(numStr)!
                return Order.D(num)
            case "C":
                return Order.C
            default: // Z
                return Order.Z
        }
    }
    
    for order in orders {
        switch order {
            case Order.U(let num):
                moveSelectRow(-num)
            case Order.D(let num):
                moveSelectRow(num)
            case Order.C:
                removeSelectRow()
            break
            case Order.Z: 
                restoreRow()
            break
            default: break
        }
    }
    
    var result = Array(repeating: "O", count: n)
    for deleteRow in recentlyDelRows {
        result[deleteRow] = "X"
    }
    
    return result.joined()
}

func moveSelectRow(_ move: Int) {
    if move > 0 {
        (0..<move).forEach { _ in
                            selectRow = linkedList[selectRow][1]
        }
    } else {
        (move..<0).forEach { _ in
                            selectRow = linkedList[selectRow][0]  
        }
    }
}

func removeSelectRow() {
    recentlyDelRows.append(selectRow)
    
    let pastIndex = linkedList[selectRow][0]
    let nextIndex = linkedList[selectRow][1]
    
    if pastIndex >= 0 {
        linkedList[pastIndex][1] = nextIndex
    }
    
    if nextIndex == linkedList.count {
        selectRow = pastIndex
        linkedList[pastIndex][1] = nextIndex
    } else {
        selectRow = nextIndex
        linkedList[nextIndex][0] = pastIndex
    }
}

func restoreRow() {
    let removedIndex = recentlyDelRows.removeLast()
    
    let pastIndex = linkedList[removedIndex][0]
    let nextIndex = linkedList[removedIndex][1]
    
    if pastIndex > 0 {
        linkedList[pastIndex][1] = removedIndex
    }
    
    if nextIndex < linkedList.count {
        linkedList[nextIndex][0] = removedIndex
    }
}

후기

시간 복잡도 실패 해결하느라 고생했던 문제.
처음에는 Array로 간단 명료하게 풀었습니다.
하지만 시간 복잡도에서 우르르르 실패를 격고 해결방안을 고민했습니다.

첫번째로는 cmd 반복문에서 매번 문자열을 파싱하고 비교하느라 오래걸리는게 아닌가해서 enum으로 교채했습니다.
그래도 시간 복잡도 전부 실패...

두번째로는 링크드리스트 형식을 도입해서 선택 row를 이동시킬 때 삭제된 row를 판별하는 반복문을 없앰으로서 해결!

문제 푸는 내내 머리속으로 링크드리스트를 도입해야하는거 아냐? 라는 생각이 계속 들었지만
링크드리스트 방식으로하면 처리해야하는 부분도 엄청 길어지고 그냥 반복문 하나 넣어서 해결하는게 더 빠르겠지 했는데...

역시 수많은 O(1) 보다 단 하나의 O(N)을 없애야했었던...
지금 생각해보면 당연한데 후...