1️⃣ 문제

문제 - 표 편집

풀이 참조 - Kakao Tech 블로그

테크 블로그에서 풀이를 참조하니, 양방향 링크드 리스트로 풀이하는거였다!

2️⃣ 풀이 방법 및 코드

1️⃣ 처음 풀이 방법(🙅‍♀️swift로 풀면 안되는 코드)

처음에는 이 유투브 영상을 참조하여 풀었지만, swift로 이와 같은 로직으로 해결하고자 하면 풀어지지 않음! 그 이유는 이따 밝히는 걸로 하고..!

Node의 프로퍼티는 아래와 같이 정의하고,

  • isRemoved: 삭제 여부를 나타내는 Bool
  • prev: 이전 노드
  • 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개의 노드들이 하나의 같은 인스턴스를 가리키고 있었던 격이다.

아래의 사진처럼!

image

3️⃣ 최종 풀이 코드

그래서 어떻게 고쳤나면

  1. Node의 value를 삭제여부를 나타내는 Bool 대신 몇번째인지 알 수 있는 Int idx로 수정
  2. Node 인스턴스를 하나만 만들고(head), for문을 돌려 새 노드를 생성하고 링크를 연결해줌.
  3. 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()
}