표 편집 (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)을 없애야했었던...
지금 생각해보면 당연한데 후...
Author And Source
이 문제에 관하여(표 편집 (Lv.3)), 우리는 이곳에서 더 많은 자료를 발견하고 링크를 클릭하여 보았다 https://velog.io/@haze5959/프로그래머스-표-편집-Lv.3저자 귀속: 원작자 정보가 원작자 URL에 포함되어 있으며 저작권은 원작자 소유입니다.
우수한 개발자 콘텐츠 발견에 전념 (Collection and Share based on the CC Protocol.)