[Algorithm/Swift] 프로그래머스(Lv.3) - 표 편집

안녕하세요 제인입니다 :)

연결리스트를 활용하는 문제를 풀어보게 되어 해당 내용에 대해 정리해보려고 하는데요,

<프로그래머스(Lv.3) - 표 편집> 문제를 풀이하며 연결리스트(LinkedList)를 Swift로 구현하는 방법에 대해서 간단하게 정리해보겠습니다!

문제 링크

프로그래머스

문제 풀이

처음 접근

저도 처음부터 연결리스트를 써야겠다는 아이디어를 떠올리지 못해 한 번에 맞추지 못했습니다,,

선택된 행을 가리키는 포인터를 두고 명령어 케이스에 따라 알맞은 처리를 할 수 있도록(포인터 이동, 삭제된 행 인덱스 기록 등) 포인터를 이용해 구현하는 방법으로 풀이를 했었습니다. 하지만, 삽입, 삭제 연산 없이 단순히 포인터만으로 명령어에 따른 테이블의 변화를 기록하려고 하니 예외 상황을 다 따져줘야하니 코드가 복잡해지고 꼬이는 문제가 있었습니다. 그렇다고 배열을 이용해 삽입, 삭제 연산을 구현하자니 효율성 테스트에서 실패할 것이 뻔하더라구요🥺 결국 이 문제는 배열보다 더 효율적인 자료구조를 찾아 구현해야 하는 문제인데요,

Array보다 데이터 삽입, 삭제를 더 빠르게 할 수 있는 자료구조인 LinkedList를 활용해서 이 문제를 풀이할 수 있습니다!

LinkedList를 이용한 풀이 방법

해당 문제에서는 테이블의 중간 데이터를 삭제하고 다시 복구하는 등의 연산이 존재하기 때문에 연결리스트 중에서도 양방향 연결리스트를 구현해서 문제를 풀이해야합니다. 양방향 연결리스트를 구현하기에 앞서 노드는 어떻게 구성하면 좋을지(어떤 데이터를 담을지), 어떤 연산이 필요한지를 먼저 체크해야겠죠?

 

1. 노드 구성

양방향 연결리스트로 구현할 것이기 때문에 이전 노드와 다음 노드를 가리키는 포인터(prev, next)가 하나씩 필요할 것이고, 데이터 필드에는 행 번호를 저장할 것이기 때문에 Int 타입으로 선언해주면 됩니다.

 

class Node {
    var index: Int?
    var next: Node?
    var prev: Node?
    
    init(index: Int, next: Node?, prev: Node?) {
        self.index = index
        self.next = next
        self.prev = prev
    }
}

 

2. 연산의 종류

해당 문제를 풀이하기 위해 필요한 연산은 다음과 같습니다.

• 새로운 노드 삽입 (초기 테이블을 LinkedList로 구성하기 위해)
• 현재 가리키고 있는 노드 삭제 (명령어 C에 해당)
• 마지막으로 삭제한 노드 복원 (명령어 Z에 해당)
• 선택된 행 위아래로 이동 (명령어 U, D에 해당)

LinkedList 클래스에 위와 같이 필요한 연산들을 함수로 만들어두고, solution 함수 안에서 switch 문을 이용해 각 명령어에 해당하는 연산을 해서 최종적인 값을 도출하도록 아래와 같이 코드를 구성했습니다. 주석에 각 함수나 코드에 대한 간단한 설명도 함께 써두었으니 참고하면 쉽게 이해가 갈 것 같아요!(이해하는 데 크게 어려움은 없을 것 같아서 코드에 대한 자세한 설명은 생략하겠습니다.)

 

+ 해당 문제의 경우, 표의 범위를 벗어나는 이동은 주어지지 않는다는 조건이 있기 때문에 선택되는 행을 이동하는 연산(remove(), moveUp(), moveDown()에 포함)에서 테이블의 인덱스를 벗어났을 때의 예외 처리를 해주지 않았는데요, 만약 이러한 조건이 없다면 head와 tail이 nil인지를 체크해 적절한 행이 선택될 수 있도록 하는 방식으로 처리할 수 있을 것 같네요!

Swift 풀이 코드

import Foundation

class Node {
    var index: Int?
    var next: Node?
    var prev: Node?
    
    init(index: Int, next: Node?, prev: Node?) {
        self.index = index
        self.next = next
        self.prev = prev
    }
}

class LinkedList {
    var head: Node?
    var tail: Node?
    var cursor: Node?
    var isDeleted: [Bool] = []
    
    // 새로운 노드 삽입
    func append(index: Int, isInitCursor: Bool) {
        let node = Node(index: index, next: nil, prev: nil)
        if isInitCursor { cursor = node } // 가리키고 있는 노드 설정
        
        if head == nil {
            head = node
            tail = node
        } else { // 뒤에 삽입(삽입되는 노드가 새로운 tail이 됨)
            node.prev = tail
            tail?.next = node
            tail = node
        }
        isDeleted.append(false)
    }
    
    // 현재 가리키고 있는 노드 삭제
    func remove() -> Node? {
        let deleteNode = cursor
        
        cursor?.next?.prev = cursor?.prev
        cursor?.prev?.next = cursor?.next
        // 마지막 노드이면 커서를 앞노드로 설정
        cursor = deleteNode?.next == nil ? deleteNode?.prev : deleteNode?.next
        
        isDeleted[deleteNode!.index!] = true
        return deleteNode
    }
    
    // 이전 삭제 노드 복원
    func restore(node: Node?) {
        node?.prev?.next = node
        node?.next?.prev = node
        isDeleted[node!.index!] = false
    }
    
    // 커서 num만큼 위로 이동
    func moveUp(to num: Int) {
        for _ in 0..<num {
            cursor = cursor?.prev
        }
    }
    
    // 커서 num만큼 아래로 이동
    func moveDown(to num: Int) {
        for _ in 0..<num {
            cursor = cursor?.next
        }
    }
}

func solution(_ n:Int, _ k:Int, _ cmd:[String]) -> String {
    var table = LinkedList()
    var deleteStack: [Node?] = []
    
    for i in 0..<n {
        table.append(index: i, isInitCursor: i == k)
    }
    
    for command in cmd {
        let splitCommand = command.split(separator: " ")
        switch splitCommand[0] {
        case "D":
            table.moveDown(to: Int(splitCommand[1])!)
        case "U":
            table.moveUp(to: Int(splitCommand[1])!)
        case "C":
            deleteStack.append(table.remove())
        case "Z":
            table.restore(node: deleteStack.removeLast())
        default:
            break
        }
    }
    
    return table.isDeleted.map({ $0 ? "X" : "O" }).joined(separator: "")
}

 

---

[참고 자료]

Swift) 양방향 연결 리스트(Doubly LinkedList) 구현 해보기

[스위프트 알고리즘] 프로그래머스: 표 편집