1️⃣ 문제
테크 블로그에서 풀이를 참조하니, 양방향 링크드 리스트로 풀이하는거였다!
2️⃣ 풀이 방법 및 코드
1️⃣ 처음 풀이 방법(🙅♀️swift로 풀면 안되는 코드)
처음에는 이 유투브 영상을 참조하여 풀었지만, swift로 이와 같은 로직으로 해결하고자 하면 풀어지지 않음! 그 이유는 이따 밝히는 걸로 하고..!
Node의 프로퍼티는 아래와 같이 정의하고,
isRemoved
: 삭제 여부를 나타내는 Boolprev
: 이전 노드next
: 다음 노드
위 그림처럼 nodeArr라는 Node 배열에 Node를 넣어 양방향으로 링크를 연결해준다.
Up&Down 할 때는 링크를 타고 이동하면, 배열의 원소 하나 하나 접근 안하므로 효율성 문제도 해결 가능!
원소 삭제도, isRemoved
의 값만 true 변환 및 스택으로 만들어진 deletedStack
에 추가해주고, 링크 조절만 하면 된다!
복구는 삭제의 반대로!(isRemoved
의 값은 false, deletedStack
은 pop, 링크 연결 복구)
import Foundation
class Node {
var isRemoved: Bool
var prev: Node?
var next: Node?
init() {
self.isRemoved = false
self.prev = nil
self.next = nil
}
}
func solution(_ n:Int, _ k:Int, _ cmd:[String]) -> String {
let nodeArr = Array(repeating: Node(), count: n) // 삭제 여부를 담는 노드 배열
var selected: Node = nodeArr[k] // 현재 선택 행
var deletedStack = [Node]() // 삭제된 행을 담는 스택 휴지통
var answer = ""
// 링크드 리스트 연결하기
for i in 1..<n {
nodeArr[i].prev = nodeArr[i-1]
nodeArr[i-1].next = nodeArr[i]
}
// 명령어 실행
cmd.forEach {
let c = $0.first!
switch c {
case "U":
let move = $0.last!.wholeNumberValue!
for _ in 0..<move { selected = selected.prev! }
case "D":
let move = $0.last!.wholeNumberValue!
for _ in 0..<move { selected = selected.next! }
case "C":
deletedStack.append(selected)
selected.isRemoved.toggle()
let up = selected.prev
let down = selected.next
if up != nil { up!.next = down }
if down != nil {
down!.prev = up
selected = down!
} else {
selected = up!
return
}
default: // "Z"
let node = deletedStack.removeLast()
node.isRemoved.toggle()
let up = node.prev
let down = node.next
if up != nil { up!.next = node }
if down != nil { down!.prev = node }
}
}
nodeArr.forEach { answer += !$0.isRemoved ? "O": "X" }
return answer
}
2️⃣ 왜 Swift로 풀면 안되는 거야?
위 코드는 노드의 프로퍼티에 접근하는 “C”나 “Z” 수행 시 selected가 가리키는 노드만 바뀌는 것이 아니라 nodeArr의 모든 노드의 값이 바뀌는 이슈가 발생함!!!!
// 주소값 출력
for i in 0..<nodeArr.count {
withUnsafePointer(to: &nodeArr[i]) { print($0) }
}
for i in 0..<nodeArr.count {
withUnsafePointer(to: &nodeArr[i].isRemoved) { print($0) }
}
이건 참조가 잘못되었다고 생각해서 위 코드로 nodeArr의 원소인 노드의 주소와 nodeArr의 노드의 isRemoved를 출력해보니 ..
좌측 그림에서 노드의 주소는 각각 다르게 할당된 것을 알 수 있지만, 우측의 각각의 노드들이 가리키는 isRemoved의 주소값이 모두 같았다!
바로 바로 문제는,
Swift에서 Array는 struct 즉, 값 타입이기 때문에 전달인자로 전달될 때 값이 복사돼서 넘어간다.
하지만 클래스인 Node는 레퍼런스 타입이기 때문에, Array(repeating: count:)
구문에 의해 똑같은 참조값이 복사되어 n개의 노드들이 하나의 같은 인스턴스를 가리키고 있었던 격이다.
아래의 사진처럼!
3️⃣ 최종 풀이 코드
그래서 어떻게 고쳤나면
- Node의 value를 삭제여부를 나타내는 Bool 대신 몇번째인지 알 수 있는 Int
idx
로 수정 - Node 인스턴스를 하나만 만들고(head), for문을 돌려 새 노드를 생성하고 링크를 연결해줌.
- answer에 미리 “O” 또는 “X”를 담을 String 배열로
- “C”나 “Z”를 수행할 시, 노드가 가지고 있는 idx값으로 그때 그때 answer의 값을 수정한다. joined() 함수로 String return
(위 이슈랑은 상관없긴 한데, 업다운 시 X값의 범위를 고려하지 않아 이 부분도 새로 수정 ㅎㅎ )
import Foundation
class Node {
var idx = 0 // 1. 바뀐 프로퍼티
var prev: Node?
var next: Node?
}
func solution(_ n:Int, _ k:Int, _ cmd:[String]) -> String {
var node = Node() // 1. 바뀐 링크드리스트(어떻게보면 이건 head)
var selected = node // 현재 선택 행
var deletedStack = [Node]() // 삭제된 행을 담는 스택 휴지통
var answer = [String](repeating: "O", count: n)
// 링크드 리스트 연결하기 (2. 바뀐 링크 연결)
for i in 1..<n {
node.next = Node()
node.next?.prev = node
node.next?.idx = i
if i == k { selected = node.next! }
node = node.next!
}
// 명령어 실행
cmd.forEach {
let c = $0.first!
switch c {
case "U": // "U X"
let move = Int($0.split(separator: " ").map { String($0) }[1])!
for _ in 0..<move { selected = selected.prev! }
case "D": // // "D X"
let move = Int($0.split(separator: " ").map { String($0) }[1])!
for _ in 0..<move { selected = selected.next! }
case "C": // "C"
deletedStack.append(selected)
answer[selected.idx] = "X"
let up = selected.prev
let down = selected.next
up?.next = down
guard down != nil else {
selected = up!
return
}
down!.prev = up
selected = down!
default: // "Z"
let restore = deletedStack.removeLast()
answer[restore.idx] = "O"
let up = restore.prev
let down = restore.next
up?.next = restore
down?.prev = restore
}
}
return answer.joined()
}