[프로그래머스] Swift - 표 편집

https://school.programmers.co.kr/learn/courses/30/lessons/81303

프로그래머스

 

2023.08.08 기준 Level 3

 

알고리즘 공부를 위해 풀고 기록하는 글입니다!
참고만 해주시고 더 좋은 풀이법이 있다면 알려주세요!

 

아이디어

요구 사항

• n개의 데이터(행) 존재
• 처음 위치는 k번째 행
• 현재 가리키는 위치를 아래 또는 위로 변경
• 현재 가리키는 위치의 데이터 삭제 가능
• 가장 최근에 삭제했던 데이터 복구 가능

제일 먼저 떠올리는 방법은 대체로 어레이를 활용한 방법일 것입니다.

n개의 요소를 가지는 배열을 만들고 K를 가리키는 인덱스를 만듭니다.

U또는 D를 만나면 이 인덱스를 X만큼 이동시킵니다.

C를 만나면 remove(at:)을 사용하여 해당 위치의 요소를 지우고

D를 만나면 다시 insert(at:)을 사용하여 넣는 방식입니다.

 

이 방식 자체의 로직에 오류는 없지만 remove(at:)과 insert(at:)의 시간 복잡도가 O(N)이기 때문에 효율성 테스트에서 실패하게 됩니다.

 

따라서, 우리는 삭제와 삽입 작업에서 시간 복잡도를 낮추어야 합니다.

 

이 때, 적합한 자료구조가 양방향 연결 리스트입니다.

 

양방향 연결 리스트 (Doubly Linked List)

• 일반적인 연결 리스트와 다르게 각 노드가 자신의 앞 노드와 뒷 노드를 각각 가리키는 구조입니다.
• 구현에 따라 append와 remove를 O(1)로 만들 수 있습니다.

 

다음과 같이 구현 계획을 세웠습니다.

1. 양방향 연결 리스트를 활용하여 n개의 노드를 만들어 연결합니다.
2. cur 변수로 현재 인덱스의 노드를 트래킹합니다.
3. U, D 명령어를 만나면 X만큼 cur을 이동시킵니다.
4. C를 만나면 삭제할 노드 자체를 스택에 저장합니다.
5. Z를 만나면 스택에서 pop하여 얻은 노드를 다시 복구합니다.

4번에서 스택을 사용한 이유는 가장 최근에 삭제한 노드를 복구해야 하기 때문에 LIFO 구조이기 때문입니다.

스택의 타입을 [Int]가 아닌 [Node] 로 지정한 이유가 중요합니다.

 

노드 자체를 스택에 넣어야 나중에 해당 노드를 복구할 때 알맞은 위치에 O(1)로 넣을 수 있기 때문입니다.

 

흰색 부분도 노드입니다. (해당 숫자를 data로 가지는 노드를 의미)

이렇게 노드를 넣게 되면 pop을 했을 때 

prev는 0을 가지는 노드, nex는 3을 가지는 노드, data는 2인 노드가 나오게 됩니다.

그렇다면 prev와 pop한 노드를 연결하고,

next돠 pop한 노드를 연결하면 복구가 끝나는 것입니다. ➡️ O(1)

 

 

풀이

1. Node 구현

fileprivate class Node {
    var data: Int
    var prev: Node? // up
    var next: Node? // down
    
    init(data: Int, prev: Node? = nil, next: Node? = nil) {
        self.data = data
        self.prev = prev
        self.next = next
    }
}

양방향 연결 리스트이기 때문에 prev, next가 필요합니다.

 

2. Doubly Lined List 구현

fileprivate struct DoublyLinkedList {
    var cur: Node?
    var tail: Node?
    var removedNodeStack = [Node]()
    
    init() {}
    
    /// O(1)
    mutating func append(_ data: Int) {
        let newNode = Node(data: data)
        
        if tail == nil {
            tail = newNode
            cur  = newNode
            return
        }
        
        tail?.next = newNode
        newNode.prev = tail
        tail = newNode
    }
    
    /// O(X)
    mutating func moveCurrentNode(amount: Int, isUp: Bool) {
        for _ in 0..<amount {
            guard let cur = cur else { return }
            if isUp {
                self.cur = cur.prev
            } else {
                self.cur = cur.next
            }
        }
    }
    
    /// O(1)
    mutating func removeCurrentNode() {
        cur?.prev?.next = cur?.next
        cur?.next?.prev = cur?.prev
        
        removedNodeStack.append(cur!)
        
        cur = cur?.next ?? cur?.prev
    }
    
    /// O(1)
    mutating func restore() {
        let removedNode = removedNodeStack.popLast()!
        
        removedNode.prev?.next = removedNode
        removedNode.next?.prev = removedNode
    }
}

이 문제 풀이를 위한 메서드들만 구현했습니다.

 

우선, 맨 처음에 n개의 노드를 만들어 순서대로 연결을 해야하기 때문에 append 메서드를 만들었습니다.

tail은 가직 마지막 노드를 가리킵니다.

 

moveCurrentNode 메서드로 cur(current)의 위치를 조정합니다.

U를 만났다면 cur를 prev 방향으로 이동시키고

D를 만났다면 cur를 next 방향으로 이동시킵니다.

시간 복잡도가 O(X)이기 때문에 이 함수에서만 시간이 좀 소요됩니다.

 

removeCurrentNode 메서드는 C를 만났을 때 실행합니다.

현재 가리키는 노드인 cur의 연결을 끊습니다.

그리고 스택에 넣어서 보관합니다.

cur를 삭제할 노드의 next 노드로 변경하는데 이것이 nil인 경우는 마지막 노드를 삭제한 것이기 때문에 문제 조건에 따라 삭제 후에 마지막 노드가 될 노드인 cur.prev로 설정했습니다.

 

restore 메서드는 Z를 만났을 때 실행합니다.

스택에서 pop을 진행하고 원래 위치로 연결합니다.

 

3. solution 함수 구현

fileprivate func solution(_ n:Int, _ k:Int, _ cmd:[String]) -> String {
    var linkedList = DoublyLinkedList()
    
    for i in 0..<n {
        linkedList.append(i)
    }
    
    // k 위치로 이동
    linkedList.moveCurrentNode(amount: k, isUp: false)
    
    for command in cmd {
        let cmdArr = command.split(separator: " ")
        switch cmdArr.first! {
        case "U":
            let amount = Int(cmdArr.last!)!
            linkedList.moveCurrentNode(amount: amount, isUp: true)
        case "D":
            let amount = Int(cmdArr.last!)!
            linkedList.moveCurrentNode(amount: amount, isUp: false)
        case "C":
            linkedList.removeCurrentNode()
        case "Z":
            linkedList.restore()
        default:
            break
        }
    }
    
    // 삭제한 노드들의 정보만 가져와서 X로 바꾼다.
    let removedData = linkedList.removedNodeStack.map { $0.data }
    
    var result = Array(repeating: "O", count: n)
    
    for i in removedData {
        result[i] = "X"
    }
    
    return result.joined()
}

양방향 리스트에서 필요한 로직들을 충분히 추상화하여 만들었기 때문에 solution함수에서는 구현 문제처럼 상황에 따라 메서드 호출만 진행해주면 됩니다.

 

모든 cmd 작업이 끝나고 removedNodeStack에 남아 있는 노드들만 최종적으로 제거된 노드들입니다.

따라서 우선 "O"로 가득 채운 배열을 만들고 removedNodeStack에 남아 있는 데이터(최초 인덱스)들에 대해서만 "X"로 바꿔주면 됩니다.

 

 

마무리

자료 구조 문제였습니다.

요소의 삭제, 복구의 소요 시간을 줄여야했고 양방향 링크드 리스트가 이 작업에 적합했습니다.

사실 moveCurrentNode 메서드의 시간 복잡도가 O(X)이기 때문에 X가 큰 경우 시간 초과가 발생하지 않을까 했는데 다행히 그러한 테스트 케이스는 없는 것 같습니다.

 

효율성 테스트에서 1~2개 실패가 발생한다면 줄바꿈 한두개만 넣고 다시 제출하면 통과합니다! (네트워크 환경에 따라 실패하는 경우가 있는 것 같아요..!)